Left Recursion-Deterministic grammars

Question

I have a question.. Is the rule $$X \to XX|a$$ a left recursive production? To make the grammar deterministic do I have to do the following changes? $$ X \to aX' ,X' \to XX'|\varnothing$$

Answer 1

Regarding your first question, you are correct, production $$X \to XX \mid a$$ is left-recursive. As to your second question, rules $$X \to aX', \quad X' \to XX' \mid \varnothing$$ are non-left-recursive, but are still ambiguous. In particular string $aaa$ could be parsed in at least two ways:

$$a\overbrace{\Big(\underbrace{a(a\varnothing)}_{X}\underbrace{\varnothing}_{X'}\Big)}^{X'} \\\ \\ a\Big(\underbrace{a\varnothing}_{X}\underbrace{(\overbrace{(a\varnothing)}^{X}\overbrace{\varnothing}^{X'})}_{X'}\Big)$$

so this wouldn't do. Also, you don't need your grammar to be non-left-recursive for it to be non-ambiguous, e.g. $$X \to Xa \mid \varnothing.$$

I hope this helps $\ddot\smile$