Show Question
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 states,
2. $$\Sigma$$ is a finite set called the alphabet,
3. $$\delta : Q \times \Sigma \to Q$$ is the transition function,
4. $$q_0 \in Q$$ is the start sate, and
5. $$F \subseteq Q$$ is the set of accept states.

### 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 = q_0$$
2. $$r_{i+1} = \delta(r_i, w_{i + 1}) \text{ for } i = 0, ..., n - 1$$, and
3. $$r_n \in F$$

$$w$$ is rejected iff it is not accepted.

If $$A$$ is the set of all strings that machine $$M$$ accepts, we say that $$A$$ is the language of machine $$M$$ and write $$L(M) = A$$. We say that M recognizes A.

#### State machine representation

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

#### Source

Introduction to the Theory of Computation, Sipser
p35-36