Given is the regular grammar G = ({A,B}, {a,b}, P, A) with the rules

P : A → aB, a, ε (where ε is the empty word)
    B → bA, b

For this regular grammar, create an equivalent NFA.

A regular grammar is a 4 tuple G = (N, Σ, P, S).

So our NFA is made up of 2 states, A and B. The initial state is A and it's also the ending state because the rule says we have the empty word ε in the state A. If we read an a from state A, we go to the state B. But I don't know what that single a means in the first rule?

From state B, if we read a b, we go to state A. But again, what does this single b mean in this rule?

All in all I would construct the NFA for the regular grammar G like that:

enter image description here


1 Answer 1


The single $a$ indicates that if we are in state $A$, and read $a$, we must go to an ending state, same with single $b$. If we follow that, we get this automaton :

enter image description here

If we were less prudent, we would argue that if we can generate an $a$ with variable $A$ and stop, and because $A$ is an ending state, then we can put a loop on state $A$ labeled with $a$, like this :

enter image description here

But this automaton doesn't match with grammar $G$. This one recognize strings of the form $a^i$, but grammar $G$ can't generate them.

But something that can be done to lighten our automaton would be to remove state $B_f$, and count on our ending state $A$ to handle the case where we end generation with a single $b$, like the following :

enter image description here

And that actually correct, because we have : empty word on variable $A$, and a rule $B \rightarrow bA$ (In fact, we can remove from $G$ the rule $B \rightarrow b$, because it can be replaced with $B \rightarrow bA \rightarrow \epsilon$).

EDIT : As @rici said, if we apply subset construction to the last automaton, we get this one : (without dead states)

enter image description here

So this is an automaton that matches with $G$.

  • 1
    $\begingroup$ Apply the subset construction to what you say is the correct solution, to convert it to a DFA. What do you get, if not the last automaton? $\endgroup$
    – rici
    Nov 30, 2017 at 15:00
  • $\begingroup$ True. $B$ can be an ending state thanks to the rule $A \rightarrow a$. I'll edit my answer. Thank you. $\endgroup$
    – user80502
    Nov 30, 2017 at 15:09

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.