Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Consider the grammar G given by
S → ABA
A → aa | bb | aBb
B → cAc | cc
From the Pumping Lemma for Context Free Languages given
in the class notes, what length for a string u
to gauruntee that u
could be "pumped", i.e. that
we could find repeated symbols, break up into v,w,x,y,z,
Now consider the very much shorter string u = bbcaccbcaccb
- Construct the parse tree for u using grammar
- There is a path containing repeated non-terminals.
Identify the repeated non-terminals (on your parse
tree from above).
- Give me the v,w,x,y,z such that u =
vwxyz, not both w and y are the
empty string, and vwkxykz ∈ L(G).