PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
automaton (Definition)

An automaton is a general term for any formal model of computation. Typically, an automaton is represented as a state machine. That is, it consists of a set of states, a set of transitions from state to state, a set of starting states, a set of acceptable terminating states, and an input string. A state transition usually has some rules associated with it that govern when the transition may occur, and are able to remove symbols from the input string. An automaton may even have some sort of data structure associated with it, besides the input string, with which it may interact.

A famous automaton is the Turing machine, invented by Alan Turing in 1935. It consists of a (usually infinitely long) tape, capable of holding symbols from some alphabet, and a pointer to the current location in the tape. There is also a finite set of states, and transitions between these states, that govern how the tape pointer is moved and how the tape is modified. Each state transition is labelled by a symbol in the tape's alphabet, and also has associated with it a replacement symbol and a direction to move the tape pointer (either left or right).

At each iteration, the machine reads the current symbol from the tape. If a transition can be found leading from the current state that is labelled by the current symbol, it is “executed.” Execution of the transition consists of writing the transition's replacement symbol to the tape, moving the tape pointer in the direction specified, and making the state pointed to by the transition the new current state.

There are many variations of this model that are all called Turing machines, but fundamentally they all model the same set of possible computations. This abstract construct is very useful in computability theory.

Other automata prove useful in the area of formal languages. Any context-free language may be represented by a pushdown automaton, and any regular language can be represented by a deterministic or non-deterministic finite automaton.



"automaton" is owned by Logan.
(view preamble)

View style:

See Also: deterministic finite automaton, non-deterministic finite automaton, non-deterministic pushdown automaton

Other names:  state machine
Also defines:  Turing machine

Pronunciation (guide):
 automaton: /aw-to'm*-t*n/, /aw-to'm*-ton/

Cross-references: non-deterministic finite automaton, regular language, pushdown automaton, context-free language, languages, area, theory, variations, iteration, right, finite, current, alphabet, structure, even, string, states, term
There are 17 references to this entry.

This is version 4 of automaton, born on 2002-02-23, modified 2002-05-24.
Object id is 2550, canonical name is Automaton.
Accessed 6344 times total.

Classification:
AMS MSC68Q45 (Computer science :: Theory of computing :: Formal languages and automata)
 03D05 (Mathematical logic and foundations :: Computability and recursion theory :: Automata and formal grammars in connection with logical questions)

Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
rate | post | correct | update request | add derivation | add example | add (any)