CFG of Language which contains equal # of a's and b's

Question

I've tried this

S -> e(Epsilon)

S -> SASBS

S -> SBSAS

A -> a

B -> b

Can someone verify if this is correct.

Ciapas

Answer 1

Your grammar is correct. Here is the proof.

First, we show that your grammar generates only strings with an equal number of a and b. Note that all productions with S on the LHS introduce an equal number of A as they do B. Therefore, any string of terminals derived from S will have an equal number of a and b.

Next, we show that all strings of a and b can be derived using this grammar. We proceed using mathematical induction.

Base case: S -> e and both S -> SASBS -> ASBS -> aSBS -> aBS -> abS -> ab and S -> SBSAS -> BSAS -> bSAS -> bAS -> baS -> ba, so the three shortest string in the language are generated by the grammar. There are no other strings in the language of length less than 4.

Induction hypothesis: all strings of length up to 2k in the language are generated by the grammar.

Inductive step: we must show all strings of length 2(k + 1) in the language are also generated by the grammar. If w = axb or w = bya for some strings x and y, then x and y are strings of length 2k in the language and are therefore generated by the grammar. In this case, we can use the same derivation with an extra application of either S -> SASBS -> ASBS -> aSBS -> aSbS -> aSb or S -> SBSAS -> BSAS -> bSAS -> bSaS -> bSa and then use the derivation for x or y to complete the derivation, yielding w. If, instead, w = axa or w = byb, then x or y is a string with exactly two more b than a or a than b. In this case, there must be a prefix p of w with |p| < |w| such that p is also a string in the language (see lemma below). If the prefix p is a word in the language, and w = pr, then r must also be a word in the language, so w must be the concatenation of two words in L. These words both have length less than |w| so less than 2(k + 1) and are generated by the grammar. If they are generated by the grammar then they are of the form SaSbS or SbSaS and their concatenation can be derived using the grammar by using the productions in the proper sequence. That is, S -> SASBS -> SASBSBSAS -> aSbSbSa = aSbS bSa <- aSbS SbSa (we are of course free to choose S -> e in that last reverse step justification).

Valentin