Consider the following expression grammar G: E → E

Home » Theory of Computation » Theory of computation miscellaneous » Question

Consider the following expression grammar G:
E → E - T | T
T → T + F | F
F → (E) | id
Which of the following grammars is not left recursive, but is equivalent to G?

1. E → E - T | T
  T → T + F | F
  F → (E) | id
2. E → TE '
  E ' → -TE ' | ∈
  T → T + F | F
  F → (E) | id
3. E → TX
  X → -TX | ∈
  T → FY
  Y → + FY | ∈
  E → (E) | id
4. E → TX | (TX)
  X → - TX | +TX | ∈
  T → - id

Correct Option: C

E → E - T |
T → T + F | F
F → ( E ) | id
Using the rule for removal of left recursion is
A → Aα / β
A → βA '
A ' → α A ' / ∈
Then, the given grammar is written as :-
E' → −TE' / ∈
E → +TE '
T ' → + FT ' / ∈
T → FT '
F → (E) | id
Now by putting E ' as X and T ' as Y, then
X → −TX / ∈
E → TX
Y → +FY / ∈
T → FY
F → (E) | id
Hence option (c) is correct.