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, then $L(G)$ is infinite.
Grammars with long derivation generate an infinite language
Frank
- 147
- 7