# Proving that L(G) is the language defined by the CFG G

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?

• what do you mean by na(w) number of $a$'s in w?
– lox
Mar 26, 2019 at 20:45
• @lox yes, sorry i will edit this in the question Mar 26, 2019 at 20:47
• 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? Mar 27, 2019 at 1:35
• 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. Mar 28, 2019 at 21:14
• cs.stackexchange.com/q/11315/755
– D.W.
Aug 23, 2019 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.