Discrete Mathematics/Finite state automata

From Wikibooks, open books for an open world
< Discrete Mathematics
Jump to: navigation, search

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)