# Questions tagged [normal-forms]

Questions about normal forms in various contexts, for example normal forms of context-free grammars (Chomsky normal form, Greibach normal form), of formulas (conjunctive normal form, disjunctive normal form), and others.

75 questions
Filter by
Sorted by
Tagged with
93 views

396 views

### Can any ambiguous context-free grammar be converted into Chomsky normal form? [closed]

Can an ambiguous context-free grammar be converted into Chomsky normal form? I think the answer is yes.
284 views

### Can every CFG be converted into an equivalent CFG of this form?

Question: Show that every CF grammar G = (V,T,S,P) can be converted into an equivalent CFG in which every production is of the form A → xBC or A → ϵ, where x ∈ T U {ϵ} and A,B, and C are variables. ...
2k views

### Chomsky or Greibach Normal Form?

I tried to solve this exercise: Discuss the normal forms (CNF or GNF) of a grammar with productions: $S\rightarrow BC | CB$ $B\rightarrow cB | c$ $C\rightarrow cC | \epsilon$ Same request with ...
63 views

### Can minimal CNF contain clause longer than initial CNF?

Let $\Phi$ be a k-CNF and $\Phi_{min}$ be a minimal CNF (one that contains smallest amount of literal occurences) that is equal to $\Phi$. Can $\Phi_{min}$ contain a clause of size $m > k$? What ...
93 views

### Growth of non-terminating beta reductions in lambda calculus

There are some terms in lambda calculus that don't really have a normal term. My question is for a term like the following: $$T \overset{def}{=} \lambda f. (\lambda x. \; f \; (f \; (f \; x)))$$ $T$ ...
336 views

### Proof any CFG can be converted to GNF

I studied algorithm for converting grammars to GNF and was wondering about a proof that any CFG can be converted into GNF. I found this paper - ENGELFRIET, Joost. An Elementary Proof of Double ...
357 views

### For every context-free grammar, is there an equivalent grammar in Chomsky normal form?

I thought that, for every CFG, there is an equivalent grammar in CNF. I was told this is false. Can someone explain to me why this is false and possibly provide a counter example?
68 views

358 views

### Can every context free grammar be transformed into equivalent grammar of this form?

Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda$ ) where $a \in V_t$ and $A,B,C \in V_n$ with rewriting rules of ...
5k views

### Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

I would like to know how they obtained the expression $2n-1$ as said from the excerpt of article (p.3): The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters ...
876 views

### Converting context-free grammar to Chomsky/Greibach Normal Form

Is it necessary to remove all lambda productions, unit productions and useless productions from a context free grammar(CFG) before converting to Chomsky Normal Form(CNF) or Greibach normal form (GNF). ...
4k views

### Converting CNF to GNF

I'm studying context free grammars and I can grasp how to create context free grammars given a set notation, and now to convert these context free grammars to Chomsky Normal form but I am utterly ...
434 views

### Canonical representation of programs

I'm working on some compiler software, and I'm looking for information on canonical forms for expressing software, algorithms, mathematical expressions (including predicate logic), etc. I assume ...
1k views

### Convert a CFG into CNF

I'm still new to CFG and CNF and have trouble sometimes understanding the concepts. I'm trying to convert this CFG into Chomsky Normal Form: ...
102 views

### how to compute functional dependencies and MVDs after decomposition?

Let's say we have a relation $R$ with a set of functional and multivalued dependencies $F$, and we found a dependency that violates some normal form. Then we decompose $R$ into $R_1$ and $R_2$. How to ...
429 views

### Does removal of unit production from the grammar may increase number of total production?

There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions) (a) O(m) (b) O($m^2$) (c) O($k^m$) (d) O(\$...
876 views

### Can we remove unit productions First Before removing Null productions?

My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null ...