Problem Set #5

CS 154
due May 17, 2005

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

 

  1. Show the table that is constructed by the CYK algorithm for the string baaab and the CFG whose start symbol is S and whose productions are given below. Show two parse trees for the given string and the given grammar. 
      S → AB | BA,    A → a | AS | CA,   B → b | BS | CB,   C → a | b

  2. 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 273 of the text will convert a grammar with left-recursion to an equivalent CFG with no left-recursion.

    Find a CFG without left recursion that is equivalent to the left-recursive CFG with start symbol E and productions below. Give a parse tree for the string x+(x*y)-y in the new grammar. 

      E → E+T | E-T | T,    T → T*F | F,   F → x | y | (E)
    EXTRA CREDIT: By itself, part (c) of Exercise 7.1.11 does not handle indirect recursion. For example, in the CFG G whose production are as above except that the parentheses are removed in the final rule, E can derive sentential forms beginning with E indirectly, using the rule F → E.

    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. Show the leftmost derivation of the string x+y*z in your new grammar that corresponds to the leftmost derivation below in the old grammar.

      E ⇒ T ⇒ T*F ⇒ F*F ⇒ E*F ⇒ E+T*F ⇒ T+T*F ⇒ F+T*F ⇒ x+T*F ⇒ x+F*F ⇒ x+y*F ⇒ x+y*x

  3. Design a TM that takes as input a bit string x representing an integer n with no leading 0's, and subtracts 1 from it. More precisely, if x begins with 1, your TM should halt in state qf with the binary representation of n-1 on the tape, and the tape head should be scanning its leftmost bit (which may be a leading 0). If x begins with 0, your TM should halt immediately. You may assume that the input alphabet is {0,1}.

    Note that this problem is similar to Exercise 8.2.3 on page 328 of the text. Unlike that exercise, you don't need the $ symbol and you don't need to show the result of testing your TM on any sample input (but you will presumably want to test it without turning in the results). You should explain the purpose of each state.

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