How do I eliminate left recursion in discrete math

Question

I am working on a problem and the grammar is below.
$A\rightarrow AA$*
$\rightarrow AA+$
$\rightarrow a$
The formula for elimination is
$A\rightarrow Aα|β$
$A\rightarrow βA'$
$A'\rightarrow αA'$
I just don't know how to use that formula if I have two AA instead of just one A
$A->aA'$
$A'\rightarrow A+A'$
$\rightarrow A*A'$
$\rightarrow a$
However, I still have one $A$ in there. How do I get rid of that? Thank you

Answer 1

I hope it can help you.

Elimination of Left-Recursion

For each rule which contains a left-recursive option,

$$A \to A\alpha|\beta$$

introduce a new nonterminal A' and rewrite the rule as

\begin{align} &A \to \beta A' \\ &A' \to \alpha A'|\epsilon \end{align}

there may be more than one left-recursive part on the right-hand side. The general rule is to replace:

$$A \to A \alpha_1 | \alpha_2|...| \alpha_n|\beta_1|\beta_2| ... |\beta_m $$

by \begin{align} &A \to \beta_1 A' | \beta_2 A'| ...| \beta_m A' \\ &A' \to \epsilon | \alpha_1 A' | \alpha_2A' | ...| \alpha_n A' \end{align}

---

$ A\to AA*|AA+|a $

we can write it as:

$A\to AB|AC|a \\ B \to A* \\ C \to A+ $

---

1. $A\to AB|a :\\ \,\,\,A\to aA'\\ \,\,\,\,A' \to A*A'|\epsilon$

2. $A \to AC|a :\\ \,\,\,A \to aA'\\ \,\,\,\,A' \to A+A'|\epsilon$

combine those two:

$A \to aA'\\ A' \to A+A'|A*A'|\epsilon$

Answer 2

Is this the grammar you've come up with?

A->aA'
A'->A+A'
A'->A*A'
A'->a

If so, this grammar does not have any left-recursion, so it looks like you're already finished.

(However, shouldn't the last rule produce the empty string instead of "a"?)

Answer 3

As you mention, the formula for removing left-recursion (and replacing it with right-recursion) involves replacing all instances of this rule: \begin{gather} A \rightarrow A\alpha\ |\ \beta\\ \end{gather} with this rule: \begin{gather} A \rightarrow \beta A'\\ A' \rightarrow \alpha A'\ |\ \epsilon \end{gather}

Your grammar is given by the following rules: \begin{gather} A \rightarrow AA*\ |\ AA+\ |\ a\\ \end{gather}

Here, we must eliminate left-recursion in two places, using the above rule for each case:

1. $A \rightarrow AA*\ |\ a$ (here, $\alpha = A*$ and $\beta=a$) \begin{gather} A \rightarrow a A'\\ A' \rightarrow A*A'\ |\ \epsilon \end{gather}
2. $A \rightarrow AA+\ |\ a$ (here, $\alpha = A+$ and $\beta=a$). \begin{gather} A \rightarrow a A'\\ A' \rightarrow A+A'\ |\ \epsilon \end{gather}

Combining these, we obtain: \begin{gather} A \rightarrow a A'\\ A' \rightarrow A+A'\ |\ A*A'\ |\ \epsilon \end{gather}