# Recent questions tagged cnf

1
A grammar is said to be in Chomsky Normal Form (CNF) if every production is either of the form $A\rightarrow BC$ or of the form $A\rightarrow a$, where $A, B$, and $C$ are nonterminals, and a is a terminal. Show how to convert any grammar into a CNF grammar for the same language (with the possible exception of the empty string - no CNF grammar can generate $\epsilon$).
2
The grammar $S\rightarrow a\:S\:a \mid \:a\: a$ generates all even-length strings of $a's$. We can devise a recursive-descent parser with backtrack for this grammar. If we choose to expand by production $S\rightarrow a \:a$ first, then we shall ... following exercises are useful steps in the construction of a "Chomsky Normal Form" grammar from arbitrary grammars, as defined in Question $4.4.8$.
3
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is infinite$.$
1 vote
4
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$
5
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$ $A\rightarrow BAB \mid B \mid \epsilon$ $B\rightarrow 00 \mid \epsilon$
6
S→ AB A→ BS|b B→ SA|a INTO GNF
7
To obtain a string of n Terminals from a given Chomsky normal from grammar, the number of productions to be used is $2n-1$ $2n$ $n+1$ $n^2$
8
Eliminate ε productions, unit productions, useless symbols and then rewrite the resulting grammar in the Chomsky Normal Form (in that order) for the following two input grammars: S -> 0E0 | 1FF | ε E -> G F -> S | E G -> S | ε
9
Convert the given CFG to GNF. $S \rightarrow MN$ $M\rightarrow aMb|\epsilon$ $N\rightarrow aNb|\epsilon$
1 vote
10
Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one[note 1] which is in Chomsky normal form and has a size no larger than the square of the original grammar's size. Source https://en.m.wikipedia.org/wiki/Chomsky_normal_form
1 vote
11
State true/false In CNF , S-> espilon and Start symbol can appear on RHS side of production.
12
13
If the start symbol derives epsilon.Can we eliminate all epsilons while converting to Chomsky Normal Form?Following question from ullman the answer given they have removed the epsilon.But I think if the start symbol derives epsilon,more accurately if L(G) contains epsilon we cannot remove it. S->ASB|epsilon A->aAS|a B->SbS|A|bb
1 vote
14
E -> E+T E -> T T -> (E) T -> i
1 vote
15
As the null string belongs to the language generated by the grammar, answer of the following questions should be "none of these"?
1 vote
16
Convert the following context free grammar into Chomsky Normal Form: $S \rightarrow ASA | aB$ $A \rightarrow B | S$ $B \rightarrow b | \epsilon$ Does the appearance of starting symbol S at RHS impacts the conversion from CFG to CNF?
1 vote
17
Given answer is (a) but L->AB i think it is wrong because A and B produce something else Previously, so instead of L->AB there would have given like L->MN M->c1 and N->S then it was correct . if I am wrong please correct me.
1 vote
18
Is it mandatory in GNF that first element in production must be terminal(I am considering there is no Left recursion) Is it mandatory in CNF that in production only two nonterminal or terminal should be there Can we not take in one production as two nonterminal and one terminal OR one terminal and two nonterminal
19
S->ASB A->aASA | a | ϵ B->SbS | A | bb Convert this grammar into Chomsky Normal Form