Problem Set #4

CS 154
due April 21, 2009

The problems are worth 10 points each.
 
  1. Let L be the language of Problem 2 of Problem Set 1. Find a right-linear grammar (in the sense of Exercise 5.1.4, p. 182 of the text) that generates L.

  2. Find a PDA that accepts the language {0p1q2r | p≥0, q≥0, r>p}. Say whether your PDA is accepting by final state or by empty stack. Show how the string 011222 is accepted by your PDA.

  3. Use the algorithm of Section 6.3.1 of the text to find a PDA M such that N(M) is the language generated by the CFG whose rules are given below and whose start symbol is S. This grammar generates the strings over {0,1} with more 1's than 0's. Find an accepting computation for the resulting PDA on the string 1011101. 
        S → X | Y
    X → 0X1 | 1X0 | XX | ε
    Y → YX | XY | YY | 1

  4. Use the algorithm of Section 6.3.2 of the text to find a CFG that generates N(M), where M is the PDA whose transition function is given below. 
    δ(q0, 0, Z0) = {(q0, 0Z0), (q0, 00Z0)}
δ(q0, 0, 0) = {(q0, 00), (q0, 000)}
δ(q0, ε, 0) = {(q1, 0}}
δ(q1, 1, 0) = {(q1, ε)}
δ(q1, ε, Z0) = {(q1, ε)}