Consider the language B = L(G), where G is the grammar given in Exercise 2.13. The pumping lemma for context-free languages, Theorem 2.34, states the existence of a pumping length p for B. What is the minimum value of p that works in the pumping lemma? Justify your answer.

Exercise 2.13.

Let G = (V, Σ, R, S) be the following grammar. V = {S, T, U}; Σ = {0, #}; and R is the set of rules:

S → T T | U

T → 0T | T 0 | #

U → 0U00 | #

a. Describe L(G) in English.

b. Prove that L(G) is not regular.