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

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Executable UML - Covers compiler issues but no code
cover Executable UML - concentrates on patterns

cover Fast Track UML 2.0 - useful for people who know some UML but are upgrading to 2.0

Commercial Software Shop

Where I can, I have put links to Amazon for commercial software, not directly related to this site, but related to the subject being discussed, click on the appropriate country flag to get more details of the software or to buy it from them.

cover JBuilder - There is also a free version of Jbuilder at borland website . However its licence conditions are quite restrictive so you may prefer another java IDE.

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

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