Problem Set #5

CS 154
due May 12, 2009

The problems are worth 10 points each, except that Problem 6 has 20 points of extra credit.

 

  1. Find a CFG without useless symbols, unit productions, or εproductions that is equivalent to G, where G has start symbol S and the productions (rules) below. Note that ε is not in L(G).

       S → ABA | CE | gGA
   A → ε | aA | AB
   B → b | bB
   C → c | cC
   D → d | DD
   E → EE
   F → BA | ε
   G → AF

    2.  

  2. Trace the behavior of the CYK algorithm on the string 10110 and the CFG whose start symbol is S and whose productions are given below. Give a parse tree for the string that corresponds to the resulting table. 
      S → ST | TW | SS | 1,    T → TT | WX | ZY | ZW | WZ,
  X → TZ,       Y → TW,    Z → 0,        W → 1

    3.  

  3. Trace the behavior of the TM with accepting state q4 and transition function given below on the strings
    1. ε
    2. 21212
    3. 11122

    δ 1 2 B X Y
    q0 (q1, X, R) (q2, X, R)
    -
    		(q0, X, R) (q0, Y, R)
    q1 (q1, 1, R) (q3, Y, R) (q4, B, R) (q1, X, R) (q1, Y, R)
    q2 (q3, Y, R) (q2, 2, R)
    -
    		(q2, X, R) (q2, Y, R)
    q3 (q3, 1, L) (q3, 2, L) (q3, B, L) (q0, X, R) (q3, Y, L)

    Don't forget to state whether the input string is accepted or not.

    4.  

  4. Using the notational conventions of the text, determine whether the universal TM would accept the string 
     001001000100100110100100101001100010100010101111110
    If not, would the computation at least halt? Justify your answer.

    5.  

  5. Design a TM to accept the set of strings over {0,1} whose last three symbols are all the same. Please document at least the purpose of each state.

    6.  

  6. A production is left-recursive if the variable on the right-hand side also appears as the first symbol on the left-hand side. Left-recursion makes pure top-down, left-to-right parsing impossible. The construction of Exercise 7.1.11(c) on page 279 of the text will convert a grammar with left-recursion to an equivalent CFG with no left-recursion. Note that the A in the secod line of (c) should be an Ai.

    1. Find a CFG without left recursion that is equivalent to the left-recursive CFG with start symbol S and productions below. Give a parse tree for the string
      my mother 's father knew my father 's mother in russia in 1900
      in both the original grammar and the new grammar. 
        S → NP VP,           NP → Det N,   Det → my | NP 's
  VP → V NP | VP PP    N → mother | father 
  V  → knew            PP → in 1900 | in russia

    2. By itself, part (c) of Exercise 7.1.11 does not handle indirect recursion. For example, the given CFG has indirect left recursion involving the symbols Det and NP. That is, Det can derive strings of symbols beginning with Det indirectly.

      Use the techniques of the rest of the exercise to find a grammar that is equivalent to G, but has neither direct nor indirect left recursion. Give a parse tree for the string of terminals of part 1 of this problem, in the new grammar.