6
$\begingroup$

So I am learning about DFA and NFA, and I need some clarification for it.

DFA

  • accept empty set
  • transition for every element in the alphabet
  • path are deterministic

NFA

  • accept the empty set and empty string
  • path are not deterministic

My question is does NFA need a transition for every element in the alphabet? If not, then let say the alphabet is {0. 1} and I am at a state without the transition for 1, do I go to the empty state or something?

Improve this question
$\endgroup$
2
  • $\begingroup$ there is no difference between the languages that an NFA can accept and the languages that a DFA can accept. For every NFA you can construct a DFA s.t L(M_nd) = L(M_d). $\endgroup$
    – alvonellos
    Commented Oct 29, 2014 at 1:34
  • $\begingroup$ The answer depends on the definition; it's possible to define DFA (equivalently) without bullet two. Furthermore, some DFA accept the empty string and some NFA don't. $\endgroup$
    – Raphael
    Commented Oct 29, 2014 at 10:16

2 Answers 2

Reset to default
11
$\begingroup$

In a DFA, if you are in state $p$ and see an input character $c$, one of three things may happen:

  1. You can consume that character (i.e., read it) and change to state $q$ ($q$ may be $p$ or not).
  2. There may not be a move defined for the pair $(p, c)$ in which case the DFA halts and rejects the input string.
  3. If the DFA is in a final state after having read all the input, it accepts the input, otherwise it rejects the input.

For an NFA, you have more possibilities:

  1. In state $p$ with input $c$ you can consume the input and change to several states $q_1, q_2, \dotsc$ .
  2. In state $p$ you can elect not to consume the input and change to several states $q_1, q_2, \dotsc$. This is called an epsilon move. In essence, your machine may change state without reading any input.
  3. As with a DFA, there may not be any move defined for the pair $(p, c)$ or $(p, \epsilon)$ in which case the NFA halts that branch of execution.
  4. If the NFA is in a final state in any particular branch of its execution and has consumed all the input, it accepts the input. If it hasn't reached any accept state after having read all the input, it rejects.

In either a DFA or an NFA, you don't need to have moves defined for all possible (state, character) pairs. If you're in state $p$ and there is no move defined for an input character, the machine (or that branch) halts and rejects.

Some people don't like this behavior and complete the automaton by creating what you apparently call an empty state and defining transitions to that state on those missing inputs. Once you're in that state (also known as a dead or error state), you never leave, no matter what the input is.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Excellent answer. As a side note: I belong to those people who "don't like this behavior". I'd require the transition function of a DFA to be a total function from pairs of state and symbol to states (i.e. case 2 in the DFA behavior above cannot occur). For many applications, for example creating a DFA which accepts the complement of a language, or creating the cross product of two automata, it is very convenient if every word corresponds to a path through the automaton. $\endgroup$
    – Hoopje
    Commented Oct 30, 2014 at 18:30
  • $\begingroup$ @Hoopje. Though pedagogically I find that it's easier for many of my students not to have to worry about a "full" FA, I'd certainly agree with your last two applications. In fact I'd go further and change your "it is very convenient..." to "it's a real pain not to have...". $\endgroup$
    – Rick Decker
    Commented Oct 30, 2014 at 20:16
3
$\begingroup$

No, NFAs can have any number of transitions for a given symbol1 from a state. If the NFA gets into the situation where the current symbol from the input has no transition from the current state, then the current path fails. If every possible path fails (in this way, or if it fails to reach an accept state at the end of the input) the NFA rejects the input.

  1. Any sensible number of course; being an integer in the range 0 to the number of states inclusive.
Improve this answer
$\endgroup$
6
  • $\begingroup$ When do I will make a transition to the empty state? And does empty state count as a state? $\endgroup$
    – holidayeveryday
    Commented Oct 29, 2014 at 0:50
  • $\begingroup$ @holidayeveryday whenever you are in a state with no transition for the symbol you're looking at. Normally the "empty state" is not a actual state, but you can formalise it if you want. If you prefer DFAs to have explicit transitions for every symbol, then the sink or reject state is the "empty" state, you can put such a state into an NFA. $\endgroup$
    – Luke Mathieson
    Commented Oct 29, 2014 at 3:30
  • $\begingroup$ @holidayeveryday, also, see Rick Decker's answer. $\endgroup$
    – Luke Mathieson
    Commented Oct 29, 2014 at 3:31
  • $\begingroup$ You have to be a bit careful here: if there is no transition for the current symbol from the current state, then the current path is aborted, but there may still be others (i.e. it doesn't automatically mean that the input is rejected). $\endgroup$
    – Klaus Draeger
    Commented Oct 29, 2014 at 15:23
  • 1
    $\begingroup$ @holidayeveryday, there is no "empty state", the NFA moves to (one state of) a set of states on each step. If the set is empty, it means that the automaton is stuck (has nowhere to go). $\endgroup$
    – vonbrand
    Commented Feb 23, 2020 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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