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?


1 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$.

accepring 00 and 01

  • $\begingroup$ Thank you! I think I see how this works. Just to make sure: non-isomorphic NFAs just mean that the NFAs do not have exactly the same transitions for each state, is this correct? $\endgroup$
    – x_Xbd
    Feb 23, 2023 at 16:12
  • $\begingroup$ Correct. This is called non-isomorphic (and not unequal) because the states can have different names. Just like with graphs (except here also edges are labelled and we distinguish initial and final states). $\endgroup$ Feb 23, 2023 at 21:35

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.