S -> aSa
S -> bSa
S -> ε

S -> aSb
S -> aSbb
S -> aSbbb
S -> ε

S -> XY
X -> aXbbb
X -> abbb
Y -> bbbbYa
Y -> bbbba

We assume there are an infinite number of $ symbols at the bottom of the stack! i.e. once you pop a $ you will see another $ under it (-:

For all context-free languages L,

There exists a constant N such that

For all w in L with |w| ≥ N,

There exists u, v, x, y, and z such that w = uvxyz, |vxy| ≤ N and |vy| ≥ 1, and

For all i ≥0, uvⁱxyⁱz is in L.

S -> aB
S -> bA
A -> aS
A -> bAA
A -> a
B -> bS
B -> aBB
B -> b

1. Show the parse tree for w = abaabb. Pick the top two repeating B's in a path from root to leaf, and separate w into 5 parts u, v, x, y, and z as the Pumping Lemma suggests. Show the dotted lines which separate w into five parts.

   
   

2. Modify the parse tree of part a by replacing the lower B's sub-tree with the upper B's subtree. This will result in v and y repeating twice. Show the dotted lines which separate the leaves into the seven parts: u,v,v,x,y,y,z.

   
   

1. L(a(a+b)^*) ∩ ODDPALINDROME

   Yes, because intersection of a regular language and a context-free language is context-free.

2. { w | w is not in EVENEVEN }

   Yes, because regular languages are closed under complementation, and every regular language is context-free.

3. EQUAL ∪ EVENEVEN

   Yes, because EQUAL is context-free, EVENEVEN is regular and therefore context-free, and context-free languages are closed under union.

4. EQUAL ∩ {aⁿbⁿaⁿ | n ≥ 1 }

   Yes, because this language is empty and every empty language is regular and therefore context-free.

Note: ODDPALINDROME is the set of palindromes with odd length, EVENEVEN is the set of words with even number of a's and even number of b's, and EQUAL is the set of words with equal number of a;s and b's.