Introduction to Computation

11Dec/080

Introduction to Computation

We need to define exactly what we mean by a computation (at a much higher level than a line of programming), there are various mathematic models for doing so which we considor in the field of the Theory of Computation. Such examples include the Turing Machine model, push-down automaton and finite-state automaton. (Most though commonly we only considor the Turing Machine model).

In the field of the theory of computation we tend to be concerned with two fields:

Computability Theory (Whether a problem can actually be solved by computation)
Complexity Theory (If a problem can be solved, whether it be solved efficiently)

In order to start modeling computation, we need to introduce some vocabulary...

We can have a language () which represents computation tasks as words (). A Grammar () describes a language. Words are usually comprised of letters or symbols from an Alphabet. An Automaton () represents a real word computers, and will recognise a given language, such that it will accept a word (command) if .

Languages can be broken in various categories.

Formal Languages

A formal language is a set of words, i.e. finite strings of letters, or symbols. The inventory from which these letters are taken is called the alphabet over which the language is defined (http://en.wikipedia.org/wiki/Formal_language)

Thus in a formal language there may a nearly infinite number of possible words (although each word will be finite in length) comprised of letters from a fixed, finite alphabet of characters.

Regular Language

A regular language is a formal lanaguage which can be recognised by a deterministic finite state automaton (DFA). All finite languages are regular.

Chomsky Hierarchy

The Chomsky Hierarchy forms an order of languages:

$\mbox{Regular} \subset \mbox{Context-Free} \subset \mbox{Context-Sensitive} \subset \mbox{Turing-Recognisable}$

This order ranges from regular languages which relates to functions such as advanced text searching, context-free languages which relate to the syntax of languages such as programming languages, to general languages (those which are turing-recognisable) which cover everything a computer can do.

The Grammars of a language distinguishes its type .

Regular Languages take rules of the form $U \rightarrow aV$ or $U \rightarrow a$ where $U, V$ are variables and $a$ is a terminal or the empty string.
Context Free Languages take rules of the form $U \rightarrow s$ where U is a variable and s is a string comprised of variables and terminals.
Context-Sensitive Languages take rules of the form $t \rightarrow s$ where t and s are strings, and the length of t is less than or equal to the length of s.
Turing Recognisable Languages take rules of the form $t \rightarrow s$ where t and s are strings.