# Discrete Mathematics/Finite state automata

Formally, a Deterministc Finite Automaton is a 5-tuple where:

Q is the set of all states.

is the alphabet being considered.

is the set of transitions, including exactly one transition per element of the alphabet per state.

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 where:

Q is the set of all states.

is the alphabet being considered.

is the set of transitions, with epsilon transitions and any number of transitions for any particular input on every state.

is the single starting state.

F is the set of all accepting states.

Note that for both a NFA and a DFA, 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 , there exists a DFA such that