Practice Problems for Exam 2

1. Consider the following grammar for prefix expressions:

   E -> +EE
   E -> * EE
   E -> - EE
   E -> a
   E -> b
   

   Write leftmost and rightmost derivations for w = +*-abab. Draw the parse trees for these derivations.

2. Construct an equivalent NFA for the following regular grammar:

   S -> bb
   S -> aA
   S -> bA
   A -> ba
   A -> bb
   A -> bB
   B -> aB
   B -> bB
   B -> bC
   C -> a
   C -> b
   

3. Write a CFG for the language L = { w | w is a word in {a,b}^* and w has twice as many a's as b's }

4. Construct a CFG and a dPDA for L = { w | w is a word in {a,b}^* and w does not end with "ba" }

5. Construct a CFG and a dPDA for L = {a^pb^qc^r | p ≥ r and p ≥ 1 and q ≥ 1 and r ≥ 1 }