0

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

Question:
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.

Clint Theron
  • 47

1 Answers1

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.

Ilkka Törmä
  • 799