## Problem Set #5

### CS 154due 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.

3. 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```
4.

5. 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.

6.

7. Using the notational conventions of the text, determine whether the universal TM would accept the string
` 001001000100100110100100101001100010100010101111110 `
11. 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. 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 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. ```
12. ``` ```
``` ```