1
$\begingroup$

enter image description here

I'm reading Computer Science: An Interdisciplinary Approach. It mentioned an NFA (nondeterministic finite automaton) with a null transition, as shown above, recognizes all binary strings that do not contain bba as a substring.

I didn't quite understand why it says so. If the null transition happens before reading the bba, it stuck at state 2 and will report yes at the end?

| cite | improve this question | |
$\endgroup$
1
$\begingroup$

If a run of an automaton reaches a state where it has no legal transitions for the next input character, that run rejects immediately.

So, in your example, if the automaton makes the null transition, it can read $bb$ while staying in state $2$. But when it reads the $a$, it has no legal transition so that run rejects. Any run that stays in states $0$ and $1$ must also reject, because those two states are rejecting states. Therefore, the automaton does indeed reject all strings containing $bba$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks @david-recherby "If a run of an automaton reaches a state where it has no legal transitions for the next input character, that run rejects" So it can reject the whole input without needing to reach the end, right? $\endgroup$ – Qiang Huang Sep 28 '18 at 16:48
  • $\begingroup$ That's correct. (I added the word "immediately" to the answer to suggest this more strongly.) $\endgroup$ – David Richerby Sep 28 '18 at 16:52
  • $\begingroup$ safaribooksonline.com/library/view/computer-science-an/… In the above example, the author says it will accept ababb because we can establish the sequence of state transitions as 0-0-1-0-2-2-2. But this is not deterministic, it is only one possible result, right? $\endgroup$ – Qiang Huang Sep 28 '18 at 17:03
  • $\begingroup$ Right. The automaton is nondeterministic, so it accepts as long as there is one or more accepting run. $\endgroup$ – David Richerby Sep 28 '18 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.