Problem Set #3

CS 154
due October 28, 2004

The problems are worth 10 points each.
  1. Show using the pumping lemma that {(01)m2n | 0 <= m < =n } is not a regular language.

  2. For the DFAs M and N whose tables are given below, show using the decision algorithm given in class (or the text) that L(M) is a subset of L(N).

    M012
    *p0 p0 p1 p2
     p1 p1 p1 p1
    *p2 p1 p1p2
    		   
    N012
    *q0 q0 q1q2
    *q1 q3 q1q2
    *q2 q3 q3q2
     q3 q3 q3q3

  3. Find a context-free grammar for the language {ajbk | k is not equal to j}. (hint: consider the cases k<j and k>j separately).

  4. The unambiguous grammar given below accepts the set of algebraic expressions over the alphabet {(,),-,*,x} that have no unnecessary parentheses. The start symbol is E.

    Show that the grammar has no parses for the expressions (x-x), (x-x)-x, and x-(x*x).
    Show that the expression (x-x)*(x*x) has exactly one parse.

    E -> E-A | T
    A -> (E-A) | T
    T -> A*B | F
    B -> (E-A) | (A*B) | F
    F -> x