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:

Language

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.


metadata block
see also:

 

Correspondence about this page

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2024 Martin John Baker - All rights reserved - privacy policy.