## Models of Computation

Filter:

DFA - Deterministic finite automaton

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

• A finite set of states $Q$
• A finite set of input symbols $\Sigma$, called the alphabet
• A transition function $\delta : Q \times \Sigma \rightarrow Q$
• A start state $q_0 \in Q$
• A set of accepting states $F \subseteq Q$

NFA - Nondeterministic finite automaton

A nondeterministic finite automaton is defined by a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ consisting of:

• A finite set of states $Q$
• A finite set of input symbols $\Sigma$
• A transition function $\delta : Q \times \Sigma \rightarrow 2^Q$
• A  initial state $q_0\in Q$
• A set of final states $F \subseteq Q$

Where $2^Q$ is the power set of $Q$, i.e., the set of all subsets of $Q$.

The NFA with $\epsilon$-moves replaces the transition function with one that allows the empty string as a possible input so that one has:

• A transition function $\delta : Q \times \Sigma \cup \{\epsilon\} \rightarrow 2^Q$

IDFA - Incomplete deterministic finite automaton

An incomplete deterministic finite automaton is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ consisting of:
• A finite set of states $Q$
• A finite set of input symbols $\Sigma$, called the alphabet
• A transition function $\delta : Q \times \Sigma \to Q$, which is a partial function
• A start state $q_0 \in Q$
• A set of accepting states $F \subseteq Q$