Problem Set #4

CS 154
due April 28, 2005

The problems are worth 10 points each, except for the last, which is worth 20 points.
  1. Find a PDA that accepts the language {0p1q0r | p>0, r>0, q=p+r}. You may accept either by empty string or by empty stack. Show how the string 011100 is accepted by your PDA.

  2. Find a CFG for the language of Problem 1 (hint: this language is simply the concatenation of two CFLs, so it's probably easiest not to use the construction of Problem 4).

  3. Find a PDA that accepts L(G), where G is the CFG with start symbol E and productions below. You may accept either by empty stack or final state. Also show how your PDA accepts the string (x'∨y)^x. 
      E -> E ^ E | E ∨ E  | E' | ( E ) | V
  V -> x | y

  4. Use the algorithm of Section 6.3 of the text to construct a CFG that generates N(M) for the PDA M below. Note that N(M) is the language {0m1n0 | 0 < m < n}.
    Simplify your grammar so that it has no useless symbols, unit productions, or ε-productions.
    Give a leftmost derivation for the string 0011110 in your simplified grammar. 
      δ(q0,0,Z0) = {(q0,0Z0)}
  δ(q0,0,0) = {(q0,00)}
  δ(q0,1,0) = {(q1,ε)}
  δ(q1,1,0) = {(q1,ε)}
  δ(q1,1,Z0) = {(q2,Z0)}
  δ(q2,1,Z0) = {(q2,Z0)}
  δ(q2,0,Z0) = {(q2,ε)}