I'm preparing for exam and I came across this question, stated below, in a past exam question paper.

Consider the following FA:
figure of an finite automaton

Find an NFA (non-deterministic FA) with four states that accepts the same language.

The question paper came with a memo and the following is the answer:
figure of a non-deterministic finite automaton

I tried to find some tutorials on YouTube to explain how this conversion is done but all I could find is NFA to DFA and minimizing DFA (but here the FA must first be converted to DFA). The closest link I could find to answer my question is this one but I don't understand it. I'll will truly appreciate it if you can teach me how to do this conversion. I only have one day to learn this. Thank you.


1 Answer 1


There's no simple conversion for this that always works. You'll have to analyze the DFA, understand what language it recognizes and come up with a small NFA for that language.

In this specific example, the DFA works as follows. The two leftmost states form a strongly connected component. Reading $b$ will send you back to the beginning, which means that reading single $a$-symbols separated by one or more $b$s will not get you out of there. But as soon as you read $aa$, you get to the third state.

From the third state you have to enter one of the two remaining states, which form another strongly connected component. Reading $a$ always puts you in the upper state and $b$ in the lower one, which is accepting. So at this point you can read any sequence of symbols, and the DFA accepts if the last one is $b$.

To put this all together, the DFA accepts a word if and only if it contains $aa$ as a subword and ends in $b$. The NFA accepts exactly these words, but in a nondeterministic way: in the initial state you can read anything, then with $aa$ you can reach the third state, then you again read anything until the last symbol $b$ lets you reach the accepting state.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .