What are non-isomorphic NFAs

Question

I came across the following problem while doing my Formal Language class assignment and hope someone can give me some hints:

1. I have $\Sigma = \{0,1\}$ and $L=\{x0a \mid x \in \Sigma^*, a \in \Sigma\}$, namely $L$ contains all strings whose second-to-last character must be a $0$.
2. I have found that there are four equivalence classes of $I_L$, namely $[\epsilon], [0], [00], [01]$, and I'm able to construct a DFA using this four equivalence classes to accept the language $L$.
3. Then, I'm asked to show that there are at least three non-isomorphic NFAs of minimum size that all can accept $L$. I think the smallest NFA must have at least three states since if a NFA has only two states, this implies that there exists a single character that can be accepted by this NFA which is not true for the language we have.

Can someone provide some hints regarding how to approach this?

Answer 1

Your argument that two states are not enough seems solid. The automaton needs a simple path of length two where only the last state is accepting.

Once we know this we can play with the automaton. Create three states: initial state $0$, seen letter $0$ as state $1$, and accept after $0a$ as state $2$. From this we can add extra edges to ensure that all and only strings ending in $0$ will reach the middle state $1$.