# Construct an equivalent NFA for the given regular grammar

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:

## 1 Answer

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 :

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 :

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 :

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)

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

• 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?
– rici
Nov 30, 2017 at 15:00
• True. $B$ can be an ending state thanks to the rule $A \rightarrow a$. I'll edit my answer. Thank you.
– user80502
Nov 30, 2017 at 15:09