Given a language, define its CFG

Given

L1 = {w belongs to {a,b}* | has as many a as b}

Define a CFG G such that L(G)= L1

In my opinion these productions should be the right answer

1) S → aSa

2) S → bSb

3) S → ε

My reasoning was:

L1 contains strings like { ab,aabb,aaabbb,...etc}

Now I have a doubt: if I apply the above productions , in a nutshell:

S → aSa

I apply the 1) so I get S → aSa → aaSaa the I choose 2) an I get 开发者_如何学编程S → aSa → aaSaa → aabSbaa and then using the empty string I get the final string S → aSa → aaSaa → aabSbaa → aabbaa

Now, maybe I'm wrong but in the string aabbaathe number of a is not equal to the number of b

Any help will be highly appreciated

Joachim

---

This is a standard class exercise, which does not yet have a correct answer.

1) S -> aSb
2) S -> bSa
3) S -> SS
4) S -> ε

Any number of a's and b's in any order, including the empty string.

---

There are quite a few online class notes with the answers and proofs. Examples: here, here, here, and here to show a few.

---

Assuming the L1 is in fact {a^nb^n | n ≥ 0}, the grammar you provided cannot (as you proved yourself) produce exactly L1. To satisfy the requirement that, loosely expressed, "the number of a's on the left side of a word must be equal to the number of b's on its right side", your objective is to find a grammar that enforces that requirement after each and every one of its productions.

Another way to think about this is: you are not allowed to use productions in your grammar that do not generate an equal number of a and b.

edit: Since this isn't homework, I'll go ahead and give the answer:

V = {A}, Σ = {a, b}, S = A, and R the set of rules:

(1) A -> aAbA | bAaA
(2) A -> ε

---

Sorry maybe I'm wrong but Michael Foukarakis'solution doesn't work

Basically these two rules do not provide strings having the same number of a and b.

(1) A -> aAb

(2) A -> ε

Take A -> aAb and then apply the 1) rule, you have A -> aAb ->aaAb and then??? If you apply the 2) you end up getting A -> aAb ->aaAb ->aab

I think the right answer is:

1)S->aSbS

2)S->bSaS

3) S->ε

Even though I get strings like : abab or aababb Actually they both fulfill the initial requirements , which is :

the string must contain the same number of a and b.

(it doesn't matter how the elements are arranged..)

Comments, of course are welcome and encouraged.