Problem Set #1

CS 154
due February 12, 2009

Each problem is worth 10 points.

 

  1. For each state of the DFA M below, give a brief description of the set of strings that is taken to the state. That is, for each state q, describe {x | δ^(q0, x) = q}.

    Also give a brief description of L(M).

    A digram for M

    2.  

  2. Find a DFA that recognizes the language of strings over {0,1,2} for which no 2 occurs before a 0.

    3.  

  3. Prove by induction that if x and y are nonempty strings and x = y, then the last character of x = the last character of y.

    Recall that we are defining string equality by saying that

    You may use any theorem proved in class.