<p>First let us know about left recursion.
 A nonterminal is left-recursive if the leftmost symbol in one of its productions is itself or can be made itself by some sequence of substitutions.</p>

<p>Left recursions have to be removed because they take us into infinite recursion. Also the grammar will not be in its normalized form.</p>

<p>So coming to your question, 
G1 is a left recursive grammar and hence left recursion has to be removed.
You can check out whether they are equal or not by generating some sample strings. On removal of left recursion, you'll end up with grammar G2.</p>

CC BY-SA 3.0
2016-04-19T04:26:27.600Z
Please read [help/on-topic] to understand the scope of this site and don't answer off-topic questions. There is another site which has a broader scope where these questions might be on-topic: [cs.se]
Kaveh
CC BY-SA 3.0
2016-04-19T01:53:43.707Z
2016-04-19T02:06:38.767Z
2016-04-19T02:06:38.767Z
Sharanya
<p>Consider the grammar
G1:  A->Aα|β
G2:  A->βX
     X->αX|ϵ</p>

<p>Its was said that these two grammars are equal.
Should something like left recursion be removed? In what sense are these equal?  Am really confused at solving such grammars.</p>

CC BY-SA 3.0
2016-04-19T03:34:14.013Z
This is not a research-level question and is therefore off-topic on this site.
Lev Reyzin
<context-free>
In what way are these two context free grammar equal?
Sheetal U
# In what way are these two context free grammar equal?

(Asked by: username_0 on 2016-04-18)

Consider the grammar
G1: A->Aα|β
G2: A->βX
X->αX|ϵ

Its was said that these two grammars are equal.
Should something like left recursion be removed? In what sense are these equal? Am really confused at solving such grammars.

**Tags:** context-free

> **Comments:**
> **username_1**: This is not a research-level question and is therefore off-topic on this site.  

---

## 1 answers

### Answer by username_2 on 2016-04-19. Score: -4 | Accepted answer

First let us know about left recursion.
A nonterminal is left-recursive if the leftmost symbol in one of its productions is itself or can be made itself by some sequence of substitutions.

Left recursions have to be removed because they take us into infinite recursion. Also the grammar will not be in its normalized form.

So coming to your question,
G1 is a left recursive grammar and hence left recursion has to be removed.
You can check out whether they are equal or not by generating some sample strings. On removal of left recursion, you'll end up with grammar G2.

> **Comments:**
> **username_3**: Please read [help/on-topic] to understand the scope of this site and don't answer off-topic questions. There is another site which has a broader scope where these questions might be on-topic: [cs.se]  

---

