DFA / Regular

A finite automaton is a 5-tuple

$$ M = (Q, \Sigma, \delta, q_{0}, F), $$

where:

1. $Q$ is a finite set called the set of states,
2. $\Sigma$ is a finite set called the input alphabet,
3. $\delta: Q \times \Sigma \to Q$ is the transition function,
4. $q_{0}\in Q$ is the start state,
5. $F \subseteq Q$ is the set of accepting states.

NFA / Regular

A nondeterministic finite automaton is a 5-tuple

$$ M = (Q, \Sigma, \delta, q_{0}, F), $$

where:

1. $Q$ is a finite set of states,
2. $\Sigma$ is a finite alphabet,
3. $\delta: Q \times \Sigma_{\varepsilon} \to \mathcal{P}(Q)$ is the transition function,
4. $q_{0}\in Q$ is the start state,
5. $F \subseteq Q$ is the set of accepting states.

$P(Q)$ to be the collection of all subsets of $Q$.

PDA / CFG

A pushdown automaton is a 6-tuple

$$ M = (Q, \Sigma, \Gamma, \delta, q_{0}, F), $$

where:

1. $Q$ is a finite set called the set of states,
2. $\Sigma$ is a finite set called the input alphabet,
3. $\Gamma$ is a finite set called the stack alphabet,
4. $\delta: Q \times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon} \to \mathcal{P}(Q \times \Gamma_{\varepsilon})$ is the transition function,
5. $q_{0}\in Q$ is the start state,
6. $F \subseteq Q$ is the set of accepting states.

DPDA / DCFG

A deterministic pushdown automaton is a 6-tuple

$$ M = (Q, \Sigma, \Gamma, \delta, q_{0}, F), $$

where:

1. $Q$ is the set of states,
2. $\Sigma$ is the input alphabet,
3. $\Gamma$ is the stack alphabet,
4. $\delta: Q \times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon} \to (Q \times \Gamma_{\varepsilon}) \cup {\emptyset}$ is the transition function,
5. $q_{0}\in Q$ is the start state,
6. $F \subseteq Q$ is the set of accept states.

The transition function $\delta$ must satisfy the following condition:
for every $q\in Q$, $a\in \Sigma$, and $x\in \Gamma$, exactly one of

$$ \delta(q, a, x),\quad \delta(q, a, \varepsilon),\quad \delta(q, \varepsilon, x),\quad \delta(q, \varepsilon, \varepsilon) $$

is not $\emptyset$.

Turing Machine

A Turing machine is a 7-tuple

$$ M = (Q, \Sigma, \Gamma, \delta, q_{0}, q_{\mathrm{accept}}, q_{\mathrm{reject}}), $$

where:

1. $Q$ is the set of states,
2. $\Sigma$ is the input alphabet not containing the blank symbol $␣$,
3. $\Gamma$ is the tape alphabet, where $␣ \in \Gamma$ and $\Sigma \subseteq \Gamma$,
4. $\delta: Q \times \Gamma \to Q \times \Gamma \times {L, R}$ is the transition function,
5. $q_{0}\in Q$ is the start state,
6. $q_{\mathrm{accept}}\in Q$ is the accept state,
7. $q_{\mathrm{reject}}\in Q$ is the reject state, where $q_{\mathrm{reject}} \neq q_{\mathrm{accept}}$.

Properties

1. Every non-deterministic Turing machine has an equivalent deterministic Turing machine.
2. Every multitape Turing machine has an equivalent single-tape Turing machine.

Examples

Regular languages (DFA/NFA)

1. $L_{1} = {w\in\{0,1\}^* \mid w\text{ has an even number of 1’s}}$
2. $L_{2} = (0\mid1)^0(0\mid1)^$
3. $L_{3} = {0^n1^m \mid n,m\ge0}$
4. $L_{4} = {w\in\{a,b\}^* \mid \text{the third symbol from the right of }w\text{ is }a}$

Context-free languages but not regular (CFG/PDA)

1. $L_{5} = {a^n b^n \mid n\ge0}$

2. $L_{6} = {ww^R \mid w\in\{0,1\}^*}$ (palindromes)

3. $L_{7} = {\text{balanced parentheses over “(” and “)”}}$

4. Arithmetic expressions, e.g.

   $$ E \to E + E \mid E * E \mid (E) \mid \mathit{id} $$

Non-context-free languages (not CFG/PDA)

1. $L_{8} = {a^n b^n c^n \mid n\ge0}$
2. $L_{9} = {ww \mid w\in\{0,1\}^*}$ (tandem repeats)
3. $L_{10} = {a^p \mid p\text{ is prime}}$
4. $L_{11} = {a^n b^n c^m d^m \mid n,m\ge0}$