Math and science::Theory of Computation

# 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:

1. $$Q$$ is a finite set called the [...],
2. $$\Sigma$$ is a finite set called the [...],
3. $$\delta : Q \times \Sigma \to Q$$ is the [...],
4. $$q_0 \in Q$$ is the [...], and
5. $$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:

1. $$r_0 = [...]$$
2. $$r_{i+1} = [...] \text{ for } i = 0, ..., n - 1$$, and
3. [...]

$$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.