Question

Which of these is the correct way to remove left-recursion from this?

T -> Xα|δ

X -> Tβ

Options to remove left-recursion from above:

1.

T -> Xα|δ
X -> δβX'
X' -> αβX' | ε

2.

T -> δT'
T' -> XT' | ε
X -> βα

3.

T -> Xα | δ
X -> δβ | Xαβ

4.

T -> δXα | δ
X -> X'X | ε
X' -> αβ

Explain your reasoning for each choice.

Answer 1

Answer: Choice 2

T -> δT'
T' -> XT' | ε
X -> βα


Explanation: Left Recursion occurs if the production if of the form

A --> Ab | c
Then we write below lines to remove left recursion, we introduce epsilon transition as well
  
A-->cA'  
A' -> b | epsilon

Coming to the above example
T -> Xα|δ
X -> Tβ

We can see that T -> Tβα | δ
Hence we write T -> δT'
Then T' -> XT' | ε (epsilon is introduced )  
and X becomes βα


Thanks, PLEASE UPVOTE. Please comment if there is any concern.,