# Prove correctness of this (context-free) grammar

I created a context free grammar for the language which has words where twice as many a than b occur.

So as example, the language would accept the words baaaab and bbbaaaaaa, aab, etc.

The context free grammar is

G = ({X} {a,b}, P, X)
P: X -> XaXaXbX, XaXbXaX, XbXaXaX, epsilon (where epsilon is the empty word)


Now how can you justify the correctness of this grammar? So I'm not asking for a strict proof, just rather a way to reason the correctness of this grammar.

The smallest possible strings are aab, aba, baa.

And somewhere, in between one of these characters, you can insert any of these three possibilities or just the empty word epsilon.

You will always end up with twice as many a than b because all our combinations satisfy this condition and we are only using these conditions. So in the end the condition will be the same and be satisfied.

Would you count this as a "reasoning of correctness"? If I read what I have written once again, it sounds a bit cheap :p

In order to prove that some grammar $G$ generates a language $L$, i.e. $L= L(G)$, you need to prove two things:
• for any string $w \in L$, $G$ yields/generates $w$, i.e., $S \Rightarrow^* w$, and
• for any string $w$ (consisiting of only terminal symbols), if $G$ yields/generates $w$, then $w \in L$
In your particular example, you first need to prove that if $w$ has twice as many $a$s than $b$s then your grammar $G$ yields $w$, and if $G$ yields some string $w$ then $w$ has twice as many $a$s than $b$s. Induction on the length of $w$ or the number of steps of application of derivation rule might be helpful.