## Finite Automata

This is the simplest model of computation. It models computation which has a low amount of memory. Useful when we want to recognise patterns in data.

A finite automation can be defined by a state diagram.

It can be defined more formally by a mathematical model which is a 5-tuple: M=(Σ,S,s0,δ,F), where:

- Σ alphabet: a finite set (non-empty) of symbols.
- S = states: a finite set (non-empty) of states.
- s0 = initial state: an element of S.
- δ = transition function: δ: S × Σ -> S (in a nondeterministic finite state machine it would be δ: S × Σ -> (S1,S2,S3,S4) i.e., δ would return a set of states).
- F = final: F S is the set of final or accept states.

#### Language

Language 'A' is the set of all strings that a machine accepts.

A language is called a 'regular language' if some finite automation recognizes it.

#### Regular Operations

If 'A' and 'B' are languages then we can define the following regular operations on them:

Union | A∪B | {x|x∈A or x∈B} |

Concatenation | A•B | {xy|x∈A or y∈B} |

Star | A^{*} |
{x_{1}x_{2}x_{3}...x_{k}|k≥0 and each x_{i}∈A} |

Regular languages are closed under regular operations, that is, if 'A' and 'B' are regular languages then so are A∪B,A•B and A^{*}.

#### Markov Chains

Probabilistic counterpart of automata.