# Computational Models

## 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* {x1x2x3...xk|k≥0 and each xi∈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.