in Theory of Computation
575 views
0 votes
0 votes
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$.$
in Theory of Computation
by
575 views

1 Answer

0 votes
0 votes
If the derivation has atleast ${2^b}$ derivations , then since the grammar is in Chomsky Normal Form, then the length of the string is atleast ${2^b}$ $\Rightarrow$ the height of the tree is atleast b+1. Now from the Proof of Pumping Lemma(Not in Sipser, but in Hopcroft-Ullman) you can find that we can pump any number of strings , i.e the language is infinite.

Related questions