# Discrete Mathematics/Finite state automata

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

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

For a DFA, ${\displaystyle \delta }$ can be viewed as a function from ${\displaystyle Q\times \Sigma \to Q}$.

Example: Consider the DFA ${\displaystyle {A}=(\{p,q\},\{a,b\},\delta ,p,\{q\})}$ with transitions given by table:

${\displaystyle \delta }$ a b
p q p
q p q

It is easy to verify that this DFA accepts the input "aaa".

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

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

For a NFA, ${\displaystyle \delta }$ can be viewed as a function from ${\displaystyle Q\times (\Sigma \cup \{\epsilon \})\to P(Q)}$ where ${\displaystyle P(Q)}$ is the power set of ${\displaystyle Q}$.

Note that for both a NFA and a DFA, ${\displaystyle 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 ${\displaystyle N}$, there exists a DFA ${\displaystyle D}$ such that ${\displaystyle L(N)=L(D)}$