Do these grammars produce the same language?

113 Views Asked by At

I was solving a problem on CFG and saw this "simplification" in two of the rules. I believe these two grammars produce the same language, however I was not able to prove it. Grammar 1 :
S -> A|B
A -> B | aAb | epsilon
B -> A | bBa

Grammar 2 :
Z -> aZb | bZa | epsilon
Any help will be appreciated EDIT : fixed terminal symbols so they are correct now

1

There are 1 best solutions below

0
On BEST ANSWER

Hint you can try to prove that the language produced by this grammar is the set of words of even length with as many a is the first half as b in the second part. You can prove that with an induction on the size of the words that are produced.