Search code examples
computation-theorydfanfa

Verify wether the following answer is correct?

I am asked to write the grammar which generate the following language over the alphabet Z={a,b} M={w | numbers of b's in w is 3 modulo 4}

My Answer is

S->bP| bJ | aS

P->bQ | bK | aP

Q->bR | bL | aQ

R->bS | e | aS

L->e

will this work? Can we make it better?

Solution

  • Not sure what J, K and L are. But yes, you can probably do better; a DFA with 4 states can recognize your language, so there's definitely a regular grammar with four nonterminals:

    S -> aS | bR
R -> aR | bT
T -> aT | bU | b
U -> aU | bS | a

    This works because states S, R, T and U correspond to having seen 0, 1, 2 and 3 instances of b, modulo 4. Seeing instances of a leaves you in whatever state you were in before, while seeing b takes you to the next state. Because state u is accepting we add U -> e, and then remove the empty production in the usual way.