Eliminate this indirect left recursion

Question

The following grammar has left recursion.

X is the start simbol.

X -> Xa | Zb
Z -> Zc | d | Xa

How to remove it? Please explain it step by step.

Answer 1

-- remove Z left recursion--

X -> Xa | Zb
Z -> dZ' | XaZ'
Z' -> cZ' | empty

--next remove Z --

X -> Xa | dZ'b | XaZ'b
Z' -> cZ' | empty

--next factorize X--

X -> XaX' | dZ'b
X'-> Z'b | empty
Z'-> cZ' | empty

--next remove X recursion--

X -> dZ'bX''
X'' -> a X'X'' | empty
X' -> Z'b | empty
Z' -> cZ' | empty