The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
44 views

Can we move quantifiers to the left in predicate logic?

Say I have part of a query in the form: ∃xa(...)∧∃xb(...)∧∃xc(...), where a, b, and c are attributes and the ellipses can be anything (I'm looking for a general rule). Is this equivalent to saying ...
0
votes
0answers
24 views

Boyce-Codd Normal Form vs. 3rd Normal Form

Any schema that satisfies BCNF also satisfies 3NF. But how can this be true if BCNF does not necessarily guarantee dependency preservation, whereas 3NF guarantees dependency preservation?
1
vote
1answer
42 views

Converting to Chomsky normal form

Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form. I have S -> abC | babS | de C -> aCa |b I know what to do with the case ...
0
votes
1answer
66 views

conversion of this grammar to CNF

My task is to convert the following grammar to CNF: $S \to SS \mid (S) \mid \lambda$ after removing lambda productions: $S\to SS, S\to (S), S\to(), S\to S$ after removing unit productions: $S\to ...
1
vote
1answer
265 views

Normal form Lambda calculus expression

I need a little help with a lambda calculus reduction to normal form: $$(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)$$ It should be solved like this: $$xx(\lambda x.x)y((\lambda ...
1
vote
1answer
220 views

Are all databases reducible to this ultimate abstract database design?

I've designed a few databases in my time, and on more than one occasion the drive to abstract common elements from specific tables has led me to create generic top-level tables which contain those ...
2
votes
1answer
30 views

Chomsky form for language of single alphabet member

I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a} My approach was ...
4
votes
3answers
919 views

The importance of normal forms like Chomsky normal form for CFGs

I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't ...
1
vote
1answer
1k views

CFG to Chomsky normal form

I've read this part like 3-4 times and I'm not understanding what is going on. Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The ...
3
votes
2answers
891 views

“Applicative order” and “Normal order” in lambda-calculus

Applicative order: Always fully evaluate the arguments of a function before evaluating the function itself , like - $(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x. ...
4
votes
1answer
200 views

3CF 3-conjunctive form satisfiability

I am self studying discrete math and I am going through MIT Mathematics for CS lecture notes but they do not have solutions available. I got stuck at Problem 3.14 (pages 64-65 of this document). The ...