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:

enter image description here

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?

  • 1
    $\begingroup$ What about $aab$. Or $aaaabb$? $\endgroup$ Nov 30 '17 at 21:53
  • $\begingroup$ @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? $\endgroup$
    – cnmesr
    Nov 30 '17 at 22:03
  • 2
    $\begingroup$ The language isn't regular. $\endgroup$ Dec 1 '17 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.