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.