# Find any kind of grammar for the language

Find any kind of grammar for the language L = {w ∈ Σ* | in w there are twice as many a's than b's} and reason its correctness.

Where w means word and Σ means alphabet, in this case obviously made up of a,b.

So I imagine I can build a NFA for the language and then "transform" that NFA into a regular grammar.

A NFA for that language should look like that:

The regular grammar is G = ({A,B,C}, {a,b}, P, A)

P : A → aB, ε (where ε is the empty word)
B → bC
C → aA


How would you show the correctness of that grammar though? I think it's not sufficient to say that the NFA terminates if and only if you start reading an a, then a b and end with an a, all that in a loop. Thus twice as many a's than b's.

Is it correct like that and is there a better way of doing it?

• What about $aab$. Or $aaaabb$? Nov 30 '17 at 21:53
• @HendrikJan Oh no.. I totally forgot about that :P Thank you! Anyway, if I got it correct till here, how can you show the correctness? I think I need to show that the automata and grammar are equivalent? Nov 30 '17 at 22:03
• The language isn't regular. Dec 1 '17 at 14:04