I met a question that asked me 'Describe the language accepted by this NFA and convert it to DFA'. The question is: (sorry for my lazy but the picture is difficult to draw…)
From the first I got confused for why it isn't a DFA?? I did not see any state has simultaneously pointed a(or b) to two states…
Q(1), it is easy.
Q(2), from observation, I guess it is $a^\ast b\vert\left(a^\ast\left(ba\right)^\ast\right)^\ast$
Q(3), I use a traditional list method to convert this 'NFA' to DFA, but failed. So I have to draw a $\varepsilon-NFA$ from the Q(2)'s regular expression $a^\ast b\vert\left(a^\ast\left(ba\right)^\ast\right)^\ast$ I concluded, and then convert this $\varepsilon-NFA$ to DFA, like the following picture shows. But it seems that this result is still a NFA..
Could you please give me some hints or comments to this question? Thank you!
Best Answer
Hint: The NFA accepts a lot of strings, so think about what kinds of strings it doesn't accept. Then try to build a DFA around that.
EDIT: I guess I should elaborate a bit. This is not a general strategy, but in this case, we notice in b) that the language consists of strings that don’t contain $bb$ as a substring. We can build a DFA to accept only strings containing $bb$ as a substring. Then flip accepting/rejecting states and we have what we wanted.