NFA from regular grammars

Question

I am trying to make an NFA from this regular grammar

$$\{a^n \mid n > 0\}\cup \{b^m a^k \mid m\ge 0,k \ge 0\}\;.$$

This is what I have now.

The last part, $a\ge 0$, is the one I am not sure of.

Answer 1

As it stands, it misses in both directions: for instance, it doesn’t accept $baa$, which is in the language, and it does accept $aba$, which is not. The first thing that you need to do is remove the $a$ loop at state $0$. Then state $0$ accepts the empty word, which is in $\{b^ma^k:m,k\ge 0\}$, and state $1$ takes care of all of the words $a^n$ with $n>0$. Moreover, you’ll no longer be able to accept anything that starts with $a$ and then has at least one $b$. In fact, the resulting automaton almost works: in addition to $a^n$ for $n>0$ and the empty word, it accepts $b^ma$ for each $m\ge 0$, and it doesn’t accept anything that’s not in the language.

It still misses some words that are in the language, however: it misses every $b^ma^k$ with $m\ge 1$ and $k\ge 2$, and it misses every $b^m$ with $m\ge 1$. Making state $2$ an acceptor state takes care of the $b^m$ words; how can you take care of the $b^ma^k$ words with $m\ge 1$ and $k\ge 2$?