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


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 '17 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 '17 at 15:09

Your Answer

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

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