3
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ Depends on the definition. Use the one your professor uses. $\endgroup$ – Raphael♦ Jul 17 '16 at 21:32
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ "A state in a DFA always needs to have exactly one transition per symbol in the alphabet." -- Only in some definitions. $\endgroup$ – Raphael♦ Jul 17 '16 at 21:32

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.