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


1 Answer 1


Now how can you justify the correctness of this grammar?

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.

This is our reference question which may be helpful to prove that a language is context free.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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