NFA construction problem

Question

I need to construct an automaton that recognizes the following language of strings over the alphabet $\{a,b\}$: The set of all strings over alphabet $\{a,b\}$ with the subsequence $abba$. (A subsequence is like a substring, except it doesn't have to be consecutive characters. For example, $abaaba$ and $babbbba$ are in the language.)

Answer 1

So this worked but i am kind of what is the difference about this one and the one from MRP.

Answer 2

Your NFA accepts all strings over $\{a,b\}$ that are of length at least 3. For example, $aaa$ is in the language recognised by it, as is $bbbbbbbbab$. Notice that you are being asked for nondeterministic finite automaton, so you should make use of this. The only requirement for our language is that it should contain at least an $a$, two $b$'s and another $a$, in that order.

So let's make an NFA that reads all $a$'s and $b$'s, and then nondeterministically guesses that the $a$ that we want is coming. Then, we do the same with the two $b$'s and the last $a$. Such an NFA may look like this one.

Notice that the $a$'s and $b$'s that we require our string to have are clearly discernible in the NFA. The $\varepsilon$-transitions should be thought of as nondeterministically guessing that the $a$ or $b$ we are looking for occurs in the next symbol we are reading. If it isn't, then this nondeterministic branch fails, but then another nondeterministic branch will go through, as long as the string is in our language.

---

As an example, let's look at the string $bababa$. In the start state, we split nondeterministically into two branches, one that takes the $b$-transition and one that takes the $\varepsilon$-transition:

1) $\rightarrow b$

2) $\rightarrow \varepsilon$

Next, we see that the branch 2) can not accept the first $b$, so this branch dies. The next symbol is an $a$, so we branch again, one branch takes the $a$-transition and the other takes the $\varepsilon$-transition, and this time the $\varepsilon$-branch can actually take the $a$-transition:

1) $\rightarrow b \rightarrow a$

2) $\rightarrow \varepsilon \not \rightarrow$

3) $\rightarrow b \rightarrow \varepsilon \rightarrow a$

The next symbol in the string is $b$, so we branch again (many times!):

1) $\rightarrow b \rightarrow a \rightarrow b$

2) $\rightarrow \varepsilon \not \rightarrow$

3) $\rightarrow b \rightarrow \varepsilon \rightarrow a \rightarrow b$

4) $\rightarrow b \rightarrow \varepsilon \rightarrow a \rightarrow \varepsilon$

5) $\rightarrow b \rightarrow a \rightarrow \varepsilon$

We see that branch 4) can accept the $b$, so this one continues, whereas branch $5)$ can only accept an $a$, so this one dies. This branching process continues, and if you complete the example, you will find that one of the branches will eventually reach the accept state.

As you can see, we get many branches, and you can think of each of the $\varepsilon$-branches as the NFA nondeterministically guessing that the current symbol is the symbol we are looking for. As you can see from the example, if this guess is wrong, the branch will simply die, and then the NFA will make new guesses until it either guesses correctly or there are no more symbols left in the string.