I have a context-free grammar defined by the production S:

S → aSbS ∣ bSaS ∣ ε

I need to prove that the CFG "G" can be defined as a language L(G) where

L(G) = {w ∈ {a, b}∗ ∶ na(w) = nb(w)}.

Where na(w) = number of a's in w, and nb(w) is the number of b's in w

How can I go about proving something like this? Is there a method?

Without giving the answer away.

  • $\begingroup$ what do you mean by na(w) number of $a$'s in w? $\endgroup$ – lox Mar 26 '19 at 20:45
  • $\begingroup$ @lox yes, sorry i will edit this in the question $\endgroup$ – user102119 Mar 26 '19 at 20:47
  • $\begingroup$ Have you understood similar examples in your course material? What have you tried? Where did you get stuck? For example, have you proved the words generated by grammar must have equal number of $a$'s and $b$'s? $\endgroup$ – John L. Mar 27 '19 at 1:35
  • $\begingroup$ My answer was that there are 3 cases: 1) from any state we are in: A call is made to epsilon: the difference between a and b is unchanged. Case 2&3: Either the production aSbS or bSaS will be called, which will eventually cause a and b to be printed (exactly once each). In the recursive calls to S, the same thing happens: a and b are eventually printed once each from that recursive call (which makes the difference between a's and b's equal to zero) or epsilon is called which also doesn't change the difference between number of a's and b's. $\endgroup$ – user102119 Mar 28 '19 at 21:14
  • $\begingroup$ cs.stackexchange.com/q/11315/755 $\endgroup$ – D.W. Aug 23 '19 at 22:27

Let us denote $L'$ the language defined by the CFG $S$.

To prove $L'$ = $L$ you must do two things:

  1. prove $w' \in L' \Rrightarrow w'\in L(G)$, meaning $L' \subseteq L(G)$

  2. prove $w \in L(G)\Rrightarrow w\in L'$, meaning $L(G) \subseteq L'$

Combine proofs 1 and 2, and you get that $L' = L(G)$.

The proofs themselves are not hard, since $L'$ has a very specific structure.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.