Equivalence of two context free grammars [for the given example]

Question

I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck:

G1:

• S->e|aB|bA
• B->bS|aBB
• A->aS|bAA

G2:

• S->e|aSb|bSa|SS

I tried to apply Arden's rule in the first grammar, to variables A and B, but I think it might be bringing me to a loop since the productions are right-recursive. I'm not really good at manipulating grammars so I don't know how to proceed in the proof.

Also, the exercise has a second question:

Show that all the words generated by G1 have even length.

I thought that if I can demonstrate that G1=G2, it is easier to conclude the proof using G2, and in fact that is something I was able to do, but I miss the fundamental equivalence so as for now I only showed the property for G2...

Answer 1

Both grammars generate the language of words having an equal number of a's and b's. Here are some hints on how to prove that.

Grammar $G_1$: Prove by induction on derivation length that

1. Every word generated by $S$ has an equal number of a's and b's.

2. Every word generated by $A$ has one more a's than b's.

3. Every word generated by $B$ has one more b's than a's.

This shows that every word generated by $G_1$ has an equal number of a's and b's. For the other direction, prove by induction on word length that

1. Every word having an equal number of a's and b's can be generated by $S$.

2. Every word having one more a's than b's can be generated by $A$.

3. Every word having one more b's than a's can be generated by $B$.

This part is more complicated, though the different cases you have to consider follow closely the rules of the grammar.

Grammar $G_2$: Easy induction on derivation length shows that every word generated by $S$ has an equal number of a's and b's. For the other direction, prove by induction on the length of the word that every word which has an equal number of a's and b's can be generated by $S$, as follows.

Given a word $w$, consider the walk generated by $w$ starting at the origin in which $a$ corresponds to a step up and to the right and $b$ corresponds to a step down and to the right. The walk ends on the X axis (since the number of a's and b's is equal). Let $x$ be the prefix of $w$ corresponding to the first time in which $w$ reaches the X axis (after the empty prefix), and write $w = xy$. If $y$ is empty then $x$ must start and end with different letters, so the one of the productions $S\to aSb|bSa$ can be used, and otherwise the production $S\to SS$ can be used.