Added to Favorites

Related Searches

Nearby Words

Automata is defined as a system where energy, information and material is transformed, transmitted and used for performing some function without the direct participation of man . In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.

An automaton is a mathematical model for a finite state machine (FSM). A FSM is a machine that, given an input of symbols, "jumps" through a series of states according to a transition function (which can be expressed as a table). In the common "Mealy" variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol.

The input is read symbol by symbol, until it is consumed completely (think of it as a tape with a word written on it, that is read by a reading head of the automaton; the head moves forward over the tape, reading one symbol at a time). Once the input is depleted, the automaton is said to have stopped.

Depending on the state in which the automaton stops, it's said that the automaton either accepts or rejects the input. If it landed in an accept state, then the automaton accepts the word. If, on the other hand, it lands on a reject state, the word is rejected. The set of all the words accepted by an automaton is called the language accepted by the automaton.

Note, however, that, in general, an automaton need not have a finite number of states, or even a countable number of states. Thus, for example, the quantum finite automaton has an uncountable infinity of states, as the set of all possible states is the set of all points in complex projective space. Thus, quantum finite automata, as well as finite state machines, are special cases of a more general idea, that of a topological automaton, where the set of states is a topological space, and the state transition functions are taken from the set of all possible functions on the space. Topological automata are often called M-automata, and are simply the augmentation of a semiautomaton with a set of accept states, where set intersection determines whether the initial state is accepted or rejected.

In general, an automaton need not strictly accept or reject an input; it may accept it with some probability between zero and one. Again this is illustrated by the quantum finite automaton, which only accepts input with some probability. This idea is again a special case of a more general notion, the geometric automaton or metric automaton, where the set of states is a metric space, and a language is accepted by the automaton if the distance between the initial point, and the set of accept states is sufficiently small with respect to the metric.

Automata play a major role in compiler design and parsing.

- Q is a set of states.
- ∑ is a finite set of symbols, that we will call the alphabet of the language the automaton accepts.
- δ is the transition function, that is

- $delta:Q\; times\; Sigma\; rightarrow\; Q.$

- (For non-deterministic automata, the empty string is an allowed input).

- q
_{0}is the start state, that is, the state in which the automaton is when no input has been processed yet, where q_{0}∈ Q. - F is a set of states of Q (i.e. F⊆Q) called accept states.

Given an input letter $ainSigma$, one may write the transition function as $delta\_a:Qrightarrow\; Q$, using the simple trick of currying, that is, writing $delta(q,a)=delta\_a(q)$ for all $qin\; Q$. This way, the transition function can be seen in simpler terms: it's just something that "acts" on a state in Q, yielding another state. One may then consider the result of function composition repeatedly applied to the various functions $delta\_a$, $delta\_b$, and so on. Repeated function composition forms a monoid. For the transition functions, this monoid is known as the transition monoid, or sometimes the transformation semigroup.

Given a pair of letters $a,bin\; Sigma$, one may define a new function $widehatdelta$, by insisting that $widehatdelta\_\{ab\}=delta\_a\; circ\; delta\_b$, where $circ$ denotes function composition. Clearly, this process can be recursively continued, and so one has a recursive definition of a function $widehatdelta\_w$ that is defined for all words $winSigma^*$, so that one has a map

- $widehatdelta:Q\; times\; Sigma^\{star\}\; rightarrow\; Q.$

The construction can also be reversed: given a $widehatdelta$, one can reconstruct a $delta$, and so the two descriptions are equivalent.

The triple $langle\; Q,\; Sigma,\; delta\; rangle$ is known as a semiautomaton. Semiautomata underlay automata, in that they are just automata where one has ignored the starting state and the set of accept states. The additional notions of a start state and an accept state allow automata to do something the semiautomata cannot: they can recognize a formal language. The language $L$ accepted by a deterministic finite automaton $langle\; Q,\; Sigma,\; delta,\; q\_0,\; Frangle$ is:

- $L=\; \{\; w\; in\; Sigma^\{star\},|;widehatdelta(q\_0,w)in\; F\}$

When the set of states Q is finite, then the automaton is known as a finite state automaton, and the set of all recognizable languages are the regular languages. In fact, there is a strong equivalence: for every regular language, there is a finite state automaton, and vice versa.

As noted above, the set Q need not be finite or countable; it may be taken to be a general topological space, in which case one obtains topological automata. Another possible generalization is the metric automata or geometric automata. In this case, the acceptance of a language is altered: instead of a set inclusion of the final state in $widehatdelta(q\_0,w)in\; F$, the acceptance criteria are replaced by a probability, given in terms of the metric distance between the final state $widehatdelta(q\_0,w)$ and the set $F$. Certain types of probabilistic automata are metric automata, with the metric being a measure on a probability space.

- Visual Automata Simulator
- JFLAP
- dk.brics.automaton
- libfa
- Proyecto SEPa (in Spanish)
- Exorciser (in German)

- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (2nd Edition)
- Michael Sipser (1997).
*Introduction to the Theory of Computation*. PWS Publishing. ISBN 0-534-94728-X. Part One: Automata and Languages, chapters 1–2, pp.29–122. Section 4.1: Decidable Languages, pp.152–159. Section 5.1: Undecidable Problems from Language Theory, pp.172–183. - James P. Schmeiser, David T. Barnard (1995).
*Producing a top-down parse order with bottom-up parsing*. Elsevier North-Holland.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday September 23, 2008 at 06:19:11 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday September 23, 2008 at 06:19:11 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.