Homework 5 Solutions

1. Construct a context-free grammar AND an nPDA for the following language: L = {a^pb^qc^r | p ≥ q and p ≥ 1 and q ≥ 1 and r ≥ 1 }

   S -> XC
   
   X -> aXb
   X -> aX
   X -> ab
   
   C -> Cc
   C -> c
   

   

2. Construct an equivalent nPDA for the following CFG:

   	S -> aAA
   	A -> aS
   	A -> bS
   	A -> a
   

   Write a leftmost derivation for w = aaabaaaaa. Also, show the nPDA stack after each transition in the nPDA that accepts w.

   

3. Construct dPDAs for the following languages:

   1. L = { aⁿ b^m | n ≥ 0 and n ≠ m }

      

   2. L = { w₁cw₂ | w₁ ∈ {a,b}^* and w₂ ∈ {a,b}^* and w₁ ≠ w₂^R }

      

4. Consider the following CFG for Palindromes:

   	S -> aSa
   	S -> bSb
   	S -> a
   	S -> b
   	S -> ε 
   

   Show the parse tree for w = ababbaba, identify repeating non-terminals in a path from root to leaf, and separate w into 5 parts u, v, x, y, and z as the Pumping Lemma suggests.