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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (191)
Orphanage
Unclass'd (1)
Unproven (496)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] automaton (Definition)

An automaton is a general term for any formal model of computation. Typically, an automaton $ A$ is represented as a state machine. Specifically, $ A$ is a five-tuple $ (S,\Sigma,\delta,I,F)$, consisting of

  1. a non-empty set $ S$ of states,
  2. a non-empty set $ \Sigma$ of symbols; a pair $ (s,\alpha)$ of a state $ s\in S$ and a symbol $ \alpha \in\Sigma$ is called a configuration,
  3. a rule $ \delta$ associating every configuration $ (s,\alpha)$ a subset $ \delta(s,\alpha)\subseteq S$ of states; $ \delta$ is called a next-state relation, or a transition relation,
  4. a non-empty set $ I\subseteq S$ of starting states, and
  5. a set $ F\subseteq S$ of final states or terminating states.

Remarks.

  • A triple $ (s,\alpha,t)$ is called a transition if $ t\in \delta(s,\alpha)$, and is written $ s\stackrel{\alpha}{\longrightarrow} t$.
  • The set $ \delta(s,\alpha)$ of next states may contain one, more than one, or no elements.
  • If $ \delta(s,\alpha)$ is a singleton for every configuration $ (s,\alpha)$, then $ \delta$ can be viewed as a function (called a transition function) from the set of configurations $ S\times \Sigma$ to $ S$.
  • If $ \delta:S\times \Sigma \to S$ is a function, and in addition $ I$ is a singleton, then the automaton $ A$ is said to be deterministic. Otherwise, $ A$ is non-deterministic.
  • If $ S$ and $ \Sigma$ are both finite, then $ A$ is called a finite-state automaton, or FSA for short.

Basically, an automaton $ A$ works as follows:

when a symbol $ \alpha$ is fed into $ A$ with starting state $ q$, a set $ \delta(q,\alpha)$ of next states is reached. If one of the next states is a final state, then $ a$ is said to be accepted by $ A$. More generally, $ A$ can read strings of symbols, and the way for $ A$ reads a string $ a=\alpha_1\alpha_2\cdots \alpha_n$ of symbols works as follows:

when $ a$ is fed into $ A$ with starting state $ q$, $ A$ reads the leftmost symbol $ \alpha_1$ first and it reaches the set of next states $ \delta(q,\alpha_1)$. Take any of the possible next states, say, $ s\in \delta(q,\alpha_1)$, $ A$ reads the next symbol $ \alpha_2$, and reaches the set of next states $ \delta(s,\alpha_2)$, and so on..., until the last symbol $ \alpha_n$ has been read.
More formally, the set-valued function $ \delta$ defined on $ S\times \Sigma$ can be extended to a function $ \delta^*$ defined on $ P(S)\times \Sigma^*$, where $ P(S)$ is the powerset of $ S$ and $ \Sigma^*$ is the Kleene star of $ \Sigma$, as follows: for $ a\in \Sigma^*$,
  • $ \delta^*(\varnothing,a):=\varnothing$
  • for any non-empty subset $ Q\subseteq S$,
    $\displaystyle \delta^*(Q,a):=\bigcup_{s\in Q} \delta^*(\lbrace s\rbrace,a)$
  • for a singleton $ \lbrace s\rbrace$, $ \delta^*$ is defined inductively:
    \begin{displaymath} \delta^*(\lbrace s\rbrace ,a):= \left\{ \begin{array}{ll} \l... ...e $b\in \Sigma^*$\ and $\alpha\in \Sigma$.} \end{array}\right. \end{displaymath}

By abuse of language, we write $ \delta$ for $ \delta^*$ and $ \delta(s,a)$ for $ \delta(\lbrace s\rbrace,a)$.

In essence, $ \delta$ becomes a function from $ P(S)\times \Sigma^*$ to $ P(S)$. A string $ a\in \Sigma^*$ is accepted by $ A$ if for some starting state $ q$, $ \delta(q,a)$ contains a final state. The ability to accept finite strings is the reason why an automaton is also referred to as a (string) acceptor. The subset of $ \Sigma^*$ of all string accepted by $ A$ is called the language accepted by the automaton $ A$, and is denoted by

$\displaystyle L(A).$
Clearly, if $ F=\varnothing$, then $ L(A)=\varnothing$. Also, if $ I\cap F\ne \varnothing$, then $ \lambda \in L(A)$.

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.

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 CWoo. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: deterministic finite automaton, non-deterministic finite automaton, non-deterministic pushdown automaton, semiautomaton, quantum automaton and quantum computation, category of automata

Other names:  next-state function, terminating state, FSA
Also defines:  finite-state automaton, transition function, starting state, final state, configuration, acceptor, automata

Pronunciation (guide):
 automaton: /aw-tom*-t*n/

This object's parent.

Attachments:
product of automata (Definition) by CWoo
complement of an automaton (Definition) by CWoo
equivalent automata (Definition) by CWoo
$\epsilon$-transition (Definition) by CWoo
juxtaposition of automata (Definition) by CWoo
Kleene star of an automaton (Definition) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: non-deterministic finite automaton, regular language, pushdown automaton, context-free language, formal languages, area, iteration, right, finite set, current, alphabet, language, Kleene star, powerset, strings, finite, function, singleton, contain, relation, subset, states, state machine, term
There are 47 references to this entry.

This is version 31 of automaton, born on 2002-02-23, modified 2008-05-18.
Object id is 2550, canonical name is Automaton.
Accessed 9175 times total.

Classification:
AMS MSC: 68Q45 (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 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

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