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

Question

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.

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.