nondeterministic finite automaton

a nondeterministic finite automaton (NFA) is a 5-tuple $\text{[math]}$ , where

$\text{[math]}$ is a finite set of states,
$\text{[math]}$ is a finite alphabet,
$\text{[math]}$ is the transition function,
$\text{[math]}$ is the start state,
$\text{[math]}$ is the set of accept states.

usually such an automaton is abbreviated NFA.
we say an NFA $\text{[math]}$ accepts the string $\text{[math]}$ if we can write $\text{[math]}$ as $\text{[math]}$ , where each $\text{[math]}$ is a member of $\text{[math]}$ and a sequene of states $\text{[math]}$ exists in $\text{[math]}$ with three conditions:

$\text{[math]}$ ,
$\text{[math]}$ , for $\text{[math]}$ , and
$\text{[math]}$ .

condition 1 says that the machine starts out in the start state. condition 2 says that state $\text{[math]}$ is one of the allowable next states when $\text{[math]}$ is in state $\text{[math]}$ and reading $\text{[math]}$ . observe that $\text{[math]}$ is the set of allowable next states and so we say that $\text{[math]}$ is a member of that set. finally, condition 3 says that the machine accepts its input if the last state is an accept state.
[cite:@sipser_comp_2012 definition 1.37]

although they recognize the same class of languages (regular languages), there are a few differences between a deterministic finite automaton and a nondeterministic finite automaton. first, every state of a DFA always has exactly one exiting transition arrow for each symbol in the alphabet. NFAs violate that rule. in an NFA, a state may have zero, one, or many exiting arrows for each alphabet symbol. second, in a DFA, labels on the transition arrows are symbols from the alphabet. this NFA has an arrow with the label $\text{[math]}$ . in general, an NFA may have arrows labelled with members of the alphabet or $\text{[math]}$ . zero, one, or many arrows may exit from each state with the label $\text{[math]}$ .
how does an NFA compute? suppose that we are running an NFA on an input string and come to a state with multiple ways to proceed. the machine splits into multiple copies of itself and follows all the possibilities in parallel. each copy of the machine takes one of the possible ways to proceed and continues as before. if there are subsequent choices, the machine splits again. if the next input symbol doesn’t appear on any of the arrows exiting the state occupied by a copy of the machine, that copy of the machine dies, along with the branch of the computation associated with it. finally, if any one of these copies of the machine is in an accept state at the end of the input, the NFA accepts the input string.
if a state with an $\text{[math]}$ symbol on an exiting arrow is encountered, something similar happens. without reading any input, the machine splits into multiple copies, one following each of the exiting $\text{[math]}$ -labeled arrows and one staying at the current state. then the machine proceeds nondeterministically as before. nondeterminism may be viewed as a kind of parallel computation wherein multiple independent "processes" or "threads" can be running concurrently.
when the NFA splits to follow several choices, that corresponds to a process "forking" into several children, each proceeding separately. if at least one of these processes accepts, then the entire computation accepts.
[cite:@sipser_comp_2012 chapter 1.2 nondeterminism]

$\text{[math]}$