# Finite automata

A finite automaton (plural: automata) is a model of computation. Finite automata and their probabilistic counterpart Markov chains are useful tools when attempting to recognize patterns in data. Their formal definition has a 1-1 correspondence with a type of state diagram.

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

- \( Q \) is a finite set called the [...],
- \( \Sigma \) is a finite set called the [...],
- \( \delta : Q \times \Sigma \to Q \) is the [...],
- \( q_0 \in Q \) is the [...], and
- \( F \subseteq Q \) is the set of [...].

### Processing of input

When an automaton receives an input string, it can either accept or reject it. A string is accepted if the automaton is in an accept state once the full input string is processed. Formally this is described as:

#### String acceptance

Let \( M = (Q, \Sigma, \delta, q_0, F) \) be a finite automaton and let \( w = w_1w_2...w_n \) be a string where each \( w_i \) is a member of the alphabet \( \Sigma \). Then \( M \) accepts \( w \) iff a sequence of states \( r_0, r_1, ..., r_n \) is \( Q \) exists with three conditions:

- \( r_0 = [...] \)
- \( r_{i+1} = [...] \text{ for } i = 0, ..., n - 1\), and
- [...]

\( w \) is rejected iff it is not accepted.

If \( A \) is the set of all [...] that [...], we say that \( A \) is the [...] of machine \( M \) and write [...]. We say that M [...] A.

#### State machine representation

A finite automaton has a 1-1 correspondence with a graphical state machine representation.