Practice Problems for Exam 2: Solutions

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.

   Leftmost derivation:

   E => +EE
     => +*EEE
     => +*-EEEE
     => +*-aEEE
     => +*-abEE
     => +*-abaE
     => +*-abab
   

   Rightmost derivation:

   E => +EE
     => +Eb
     => +*EEb
     => +*Eab
     => +*-EEab
     => +*-Ebab
     => +*-abab
   

   Parse tree (same for both 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
   

   NFA:

   

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 }

   S -> SaSaSbS
   S -> SaSbSaS
   S -> SbSaSaS
   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" }

   

   CFG obtained from DFA:

   S --> aS
   S --> bA
   S --> ε
   A --> aB
   A --> bA
   A --> ε
   B --> aS
   B --> 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 }

   CFG:

   S -> aSc
   S -> aS
   S -> B
   B -> Bb
   B -> b
   

   dPDA: