Problem Set #4

CS 154
due November 18, 2004

The problems are worth 10 points each, except for #3, which is worth 20 points.
  1. Find a PDA that accepts the language {0m1n0 | 0 < m < n}. You may accept either by empty string or by empty stack.

  2. 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+x]*x. 
      E -> E + T | T
  T -> T * F | F
  F -> x | [ E ]

  3. Use the algorithm of Section 6.3 of the text to construct a CFG that generates N(P) for the PDA below.
    Simplify your grammar so that it has no useless symbols, unit productions, or ε-productions.
    Give leftmost derivations for the strings abaaba and bbbb in your simplified grammar.

    Note that N(P) is the set of nonempty, even-length palindromes over {a,b}.

    4.   δ(q0,a,Z0) = {(q1,AZ0)}
  δ(q0,b,Z0) = {(q1,BZ0)}

  δ(q1,a,A) = {(q1,AA),(q2,ε)}
  δ(q1,b,B) = {(q1,BB),(q2,ε)}
  δ(q1,a,B) = {(q1,AB)}
  δ(q1,b,A) = {(q1,BA)}

  δ(q2,a,A) = {(q2,ε)}
  δ(q2,b,B) = {(q2,ε)}

  δ(q2,ε,Z0) = {(q2,ε)}

  4. A regular grammar is a CFG in which the RHS of every production consists of ε, a single terminal symbol, or a single terminal followed by a single nonterminal. Every regular language has a regular grammar, and every regular grammar generates a regular language.

    It's relatively easy to construct a regular grammar G that accepts L(M), given a DFA M. The idea is that the sentential forms in a leftmost derivation should simply consist of the input already accepted, followed by the current state. So suppose for example that M is the DFA that we used as our first example for going from DFAs to regular expresssions (with A and B used for the names of the states). Then we want to generate the string bbccb by the derivation 

      A => bA => bbA => bbcB => bbccB => bbccbA => bbccb
    that mimics the computation of M on the string. To make this derivation legal, both for the given M and for an arbitrary DFA M, we need to construct a grammar G from M by letting V be Q, T be Σ and S be q0, and by including rules in the grammar as follows:
    1. whenever q is an accepting state, include the rule q -> ε
    2. whenever δ(q, a) = p, include the rule q -> ap

    Find a regular grammar for the language of nonempty strings over {0,1} that represent multiples of 3 in binary. Leading 0's are allowed.