Problem Set #5

CS 154
due December 9, 2004

40 points, plus 5 points extra credit -- that is, the grading scale will be based on 40 points although there are 45 points on the problem set, so that a score of 36 is guaranteed to earn an A-, a score of 32 is guaranteed to earn a B-, etc.
  1. (10 points) Show the table that the CYK algorithm constructs for the input string cabba and the grammar whose start symbol is S and whose productions are given below. If the input string is generated by the grammar, give a parse tree for the string. Otherwise, just say that it is not generated. 
       S -> ZS | XA | BX | CY
   Z -> XA | BX | CY
   Y -> XX
   X -> a | b | c
   A -> a
   B -> b
   C -> c

  2. (10 points) For the CFG G with start symbol S and productions given below, show that L(G) contains an infinite regular subset. Give an regular expression for this subset. Half credit will be given if you can show that L(G) is infinite but can't find an infinite regular subset.

      S  -> NP VP 
  VP -> VI | VT NP
  VT -> announced | believes
  VI -> arrived | sneezed
  NP -> kim | sandy | that S

  3. (10 points) Find L(M), where M is the TM with start state q0 and accepting state q4 whose transition function δ is given below. Express your answer as a regular expression (yes, this is a hint -- the answer is a regular language).

    0
    1
    2
    B
    q0 (q0,0,R) (q0,1,R) (q0,2,R) (q1,B,L)
    q1 (q2,B,R) (q3,B,R) (q4,B,R) (q0,B,L)
    q2
    -
    -
    -
    -
    q3
    -
    -
    -
    -
    q4
    -
    -
    -
    -

  4. (15 points) Say whether each of the following questions is decidable, and justify your answer in each case. Your justification may rely on any theorem or assertion in the textbook.
    1. Given a TM M, does M accept a recursively enumerable language?
    2. Given a TM M, does M accept only strings of length 1?
    3. Given a CFG G, is G ambiguous?