Question

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.

Short answer

The grammar G, be a context free grammar 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 is proved.

Step-by-step solution

Chomsky normal form

A context-free grammar, G, is said to be in Chomsky normal form (first described by

Noam Chomsky) if all of its production rules are of the form,

$A\to BC$, or

$A\to a$

Show that L(G) if infinite

The grammar G, be a context free grammar 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,

Because the grammar G, is a context free grammar in Chomsky normal form, any

derivation can only produce two non-terminals,

Hence an internal node in any parse tree using G, can only have two children.

This means that every parse tree of height k has a maximum of 2k -1.

If G, generates some string with a derivation having at least $2^b$steps, the parse tree

of that string will have at least $2^b$internal nodes.

Based on the above argument, this parse tree has height is at least b+1 , so that

there exists a path from root to leaf containing b+1 variables.

By pigeonhole principle, there is one variable occurring at least twice.

So, here use the technique in the proof of the pumping lemma to construct infinitely

many strings which all are in L(G).

Hence, the grammar G, be a context free grammar 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 is proved.