I'm preparing for exam and I came across this question, stated below, in a past exam question paper.
Question:
Consider the following FA:
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:
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.
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.