Problem Set #3

CS 154
due April 7, 2005

The problems are worth 10 points each. One problem has an extra credit portion.
  1. If r is the regular expression (01)*, then L = L(r) is a regular language. So there must be an error in any argument that claims to show that L is nonregular. Find the error in the pumping lemma argument below:

    To show that L is not regular, when given n, let w be (01)n. Let x = 0, y = 1, and z = (01)n-1. Then xz has more 0's than 1's, and so xz can't be in L. Thus the pumping lemma shows that L is not regular.

  2. For the DFAs M and N whose tables are given below, show by finding a DFA for L(M) - L(N) that L(M) is a subset of L(N).

    3. M
    0
    1
      p0 p0 p1
      p1 p2 p1
      p2 p0 p3
    *p3 p3 p3
    		     
    N
    0
    1
      q0 q1 q0
      q1 q1 q2
    *q2 q2 q2

  3. Recall that one unambiguous context-free grammar for algebraic expressions with + and * and parentheses has start symbol E and the productions 
       E -> E + T | T,
   T -> T * F | F,
   F -> (E) | Atom,
    where Atom is a variable that derives operands with no + or * or parentheses.

    Extend this context-free grammar to cover a new operator @ that has higher precedence than * and that has the property that x @ y @ z is interpreted as x @ (y @ z) and not as (x @ y) @z. You needn't give any rules for the variable Atom.

    Extra credit (2 points): Can you think of a mathematical operator that should behave this way?

  4. Let L be the set of strings over {0,1} that contain 101 as a substring. Find right-regular grammars (in the sense of Exercise 5.1.4, p. 180 of the text) for both L and its complement.