Finite Aautomaton

Definition

A finite automaton is a 5-tuple $(Q,\Sigma ,\delta ,q_0,F)$ where:

1. $Q$ is a finite set of states.
2. $\Sigma$ is a finite input Alphabet.
3. $\delta$ is the transition function,
4. $q_0\in Q$ is the start state.
5. $F\subseteq Q$ is the set of accept states.

$\delta$ has a type that depends on the specific variant of machine we are discussing, see below.

Determinism

• DFA: $\delta :Q\times \Sigma \to Q$.
• NFA: $\delta :Q\times {\Sigma }_{\epsilon }\to \mathcal{P}(Q)$, where ${\Sigma }_{\epsilon }=\Sigma \cup \{\epsilon \}$.

Equivalence

DFAs and NFAs recognize the same class of languages: Regular Language.

Proof (sketch)

NDFAs are reducible to DFAs by constructing a DFA with states $2^Q$ of the set of states reachable after some input. Some accounting is required to handle $\epsilon$ but it is relatively straight-forward.

See also

Pushdown Automaton