0

I have a few quick questions about NFAs and DFAs.

  1. Is any automaton with epsilon transitions always a NFA?

  2. Is any automaton with two paths for the same symbol from a state always a NFA? Ex. Say state 1 has two paths for input "a", is this a NFA no matter what?

  3. (Not sure if this will make sense) Say we have a NFA with a state "q0" from this state you can take epsilon or "1" to state "q1" (no other transitions). If we were to convert this NFA to a DFA, is it possible that you could get to state "q1" from "q0" with some input other than epsilon or "1"? (an answer to a quiz question showed this, not sure how it is possible)

KDecker
  • 861
  • 2
  • 11
  • 23

1 Answers1

1

  1. yes, as soon as you have epsilon transition, you are a NFA (except if it is the only transition available, but then the state is useless).

  2. Yes, this is the meaning of "Nondeterministic" in NFA

  3. The question does not really make sense, because when you convert a NFA to a DFA, you don't get the same states, so the resulting DFA does not have states q0 and q1. If you take the standard powerset construction, it has states {q0} and {q1}, and then it is possible to go from one to the other with other than "1", for instance imagine you have in the NFA a loop labeled 1 from q1 to q1 and no other transitions (other than the ones you mentioned), then 11 takes you from {q0} to {q1} in the powerset DFA.

Also, notice for the record that any DFA is also a particular NFA, just as any square is also a losange.

Denis
  • 6,945
  • 1
  • 21
  • 22
  • Here is the NFA in question in question 3, I asked a question about it. http://math.stackexchange.com/questions/941706/converting-this-nfa-to-a-dfa-how-to-do-it-by-the-method-specified – KDecker Sep 22 '14 at 15:32