# 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
2answers
93 views

1answer
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.
1answer
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. ...
1answer
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 ...
1answer
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 ...
0answers
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$ ...
1answer
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 ...
1answer
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?
0answers
68 views

1answer
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 ...
2answers
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 ...
2answers
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). ...
0answers
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 ...
2answers
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 ...
1answer
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: ...
0answers
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 ...
1answer
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(\$...
1answer
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 ...
2answers
273 views

### Why is there more frequent overflow in normalised Floating Point

I read that overflow is more frequent when we work with normalised mantissas. Why is this? Is it because when we adopt a normalised representation, our range is smaller than in a unnormalised ...
0answers
47 views

### A syntactic property of computing systems: is non-coding DNA universal?

One of the surprising aspect of the genome for lay-people is that it contains important non-coding DNA parts, which does not mean that they are all useless. I never paid so much attention to the fact, ...