S → ABA | CE | gGA A → ε | aA | AB B → b | bB C → c | cC D → d | DD E → EE F → BA | ε G → AF
10110and 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
|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.
001001000100100110100100101001100010100010101111110If not, would the computation at least halt? Justify your answer.
Ain the secod line of (c) should be an
- 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
in both the original grammar and the new grammar.
my mother 's father knew my father 's mother in russia in 1900S → 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
NP. That is,
Detcan derive strings of symbols beginning with
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.