Formal languages and theory of computation, part 1
CS 288
May 4, 2005

 

  1. Show that the regular expression (10+101)* represents the same language as is accepted by the DFA whose transition function δ is given below. The final states are q0, q2, and q3. Missing table entries represent transitions to a dead state. 
         δ   |    q0    q1    q2    q3
     ----------------------------------------
     0   |    -     q2    -     q2
     1   |    q1    -     q3    q1

     

  2. Give an example, if possible, of
    a) an undecidable question about CFGs or CFLs
    b) an undecidable problem that is in NP
    c) a CFL that is not a DCFL
    d) a problem that is complete for PS
    e) a language that is in P but whose complement is not
    f) a language that is recursively enumerable (RE) but not recursive

     

  3. Show that the CFG with start symbol E and productions given below is unambiguous. 
      E → E+T | T     T → T*F | F      F → x | y | (E)
    If you cannot put in every detail of your argument, make sure that its general outline is clear.