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, 2019 at 20:45
  • $\begingroup$ @lox yes, sorry i will edit this in the question $\endgroup$
    – user102119
    Mar 26, 2019 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, 2019 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, 2019 at 21:14
  • $\begingroup$ cs.stackexchange.com/q/11315/755 $\endgroup$
    – D.W.
    Aug 23, 2019 at 22:27

1 Answer 1


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.


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.