0

From what I understand, an NFA cannot have backtracking. For an assignment I have to have strings that always end with ab's, and I have come up with this diagram. However, I still struggle with the difference between the two and because of the backtracking, this is considered a DFA (I think?) Can someone suggest me how to tweak this into a NFA?

enter image description here

ano
  • 37

1 Answers1

0

It's deterministic. You can tell because each state has at most one outgoing arrow per symbol. This means that, no matter which state you end up in, the machine determines which state you go to next, so there's no choice, and hence no need or possibility for back-tracking.

user744868
  • 1,533
  • @XanderHenderson There is one outgoing arrow per symbol: one for $a$ and one for $b$. When parsing a word, at each step, you have only one choice of arrow to follow, depending on whether an $a$ or $b$ is next, which makes it deterministic. I don't see why this answer is incorrect. – user744868 Mar 01 '20 at 20:42
  • Ah! Okay. Thanks for the clarification. – Xander Henderson Mar 01 '20 at 20:43
  • Thank you for your answer. That makes sense. Would it be possible to have a NFA with starting state S0 with a loop of either a or b, and then an outgoing arrow for the symbol ab to final state S1? I apologize if this seems silly, I'm quite new at this. – ano Mar 01 '20 at 21:00
  • Finite automata (in the sense that I'm used to; lots of people take their own liberties with the definition) cannot have a string (like $ab$) as an outgoing arrow. However, you can achieve the same effect (with an NFA) by having two loops on the first state, then a second $a$ arrow pointing to an intermediary state, then a single $b$ arrow pointing to the final state. – user744868 Mar 01 '20 at 22:14