patternMinor
Does a NFA/DFA need a failure state?
Viewed 0 times
dfanfaneedstatedoesfailure
Problem
I'm learning for my exam in theoretical computer science and I'm not sure about it, because I got different sources with different answers. So I wanted to ask here:
If I draw a NFA/DFA and I maybe don't need the transition from a state $z_k \rightarrow z_{k+1}$ with a $0$ above the alphabet $\Sigma = \{0,1\}^*$ so I only need there a $1$, do I always need a failure state $z_F$ so that $\delta: z_k (0) \rightarrow z_F $. Or can I omit that in the drawing? Or is there a difference between DFA and NFA, so that I need to write this failure function if its an NFA but I can omit it if it's an DFA? In my exercises my prof deducted one point because I had no failure state but just one or two times..
Hope somebody can help
If I draw a NFA/DFA and I maybe don't need the transition from a state $z_k \rightarrow z_{k+1}$ with a $0$ above the alphabet $\Sigma = \{0,1\}^*$ so I only need there a $1$, do I always need a failure state $z_F$ so that $\delta: z_k (0) \rightarrow z_F $. Or can I omit that in the drawing? Or is there a difference between DFA and NFA, so that I need to write this failure function if its an NFA but I can omit it if it's an DFA? In my exercises my prof deducted one point because I had no failure state but just one or two times..
Hope somebody can help
Solution
A state in a DFA always needs to have exactly one transition per symbol in the alphabet. I have understood from a few of my classmates that some teachers omit the error-state. I however prefer to show the error-state in graphs, since it simplifies verification of determinism in a graph.
In a NFA there can be no such rule. Therefore it should work to not present a transition for the symbol (0) in this case. If the NFA would be determinized, this non existing transition, along with all other non-looping transitions would point to a error state.
In a NFA there can be no such rule. Therefore it should work to not present a transition for the symbol (0) in this case. If the NFA would be determinized, this non existing transition, along with all other non-looping transitions would point to a error state.
Context
StackExchange Computer Science Q#60683, answer score: 4
Revisions (0)
No revisions yet.