Discrete Mathematics/Finite state automata

Formally, a Deterministc Finite Automaton is a 5-tuple $D=(Q,\Sigma ,\delta ,s,F)$ where:

Q is the set of all states.
$\Sigma$ is the alphabet being considered.
$\delta$ is the set of transitions, including exactly one transition per element of the alphabet per state.
$s$ is the single starting state.
F is the set of all accepting states.

Similarly, the formal definition of a Nondeterministic Finite Automaton is a 5-tuple $N=(Q,\Sigma ,\delta ,s,F)$ where:

Q is the set of all states.
$\Sigma$ is the alphabet being considered.
$\delta$ is the set of transitions, with epsilon transitions and any number of transitions for any particular input on every state.
$s$ is the single starting state.
F is the set of all accepting states.

Note that for both a NFA and a DFA, $s$ is not a set of states. Rather, it is a single state, as neither can begin at more than one state. However, a NFA can achieve similar function by adding a new starting state and epsilon-transitioning to all desired starting states.

The difference between a DFA and an NFA being the delta-transitions are allowed to contain epsilon-jumps(transitions on no input), unions of transitions on the same input, and no transition for any elements in the alphabet.

For any NFA $N$ , there exists a DFA $D$ such that $L(N)=L(D)$

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.