The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
18 views

Does 4NF imply BCNF?

Wiki says: 4NF is the next level of normalization after Boyce–Codd normal form, but I can not see how the definition of 4NF implies BCNF. Consider the relation with 3 attributes: Country, ...
2
votes
1answer
43 views

Does Herbrand's theorem mean any first-order logic formula can be expressed in CNF?

Herbrand's theorem shows that any formula of first-order logic can be expressed as a disjunction of quantifier-free formulas of first-order logic. Is this equivalent to saying that Herbrand's theorem ...
3
votes
1answer
241 views

Difference between data duplication and data redundancy

My Computing teachers talk about data duplication and data redundancy in terms of databases as different things, but I'm struggling to differentiate them. The context is database normalisation, and in ...
2
votes
1answer
76 views

Can every DCFG be converted to DGNF?

I know you can convert every context-free grammar into Greibach normal form grammar. But can I convert every deterministic context-free grammar into deterministic Greibach normal form grammar?
1
vote
2answers
61 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
1answer
74 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
77 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 ...
-4
votes
2answers
139 views

Boolean algebra fast CNF convertion

I have been solving a "hard" boolean formula today and found a nice shortcut. So just wanted to share. When given the next formula how would you convert it to CNF? $\lnot(x \oplus y \oplus ...
0
votes
1answer
70 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
338 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
266 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
34 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
1k 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
2k 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 ...
4
votes
2answers
1k 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
210 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 ...