Automata theory

Automata theory

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.

Vocabulary

The basic concepts of "symbols", "words", "alphabets" and "strings" are common to most descriptions of automata. These are:; Symbol : An arbitrary datum which has some meaning to or effect on the machine. Symbols are sometimes just called "letters".; Word: A finite string formed by the concatenation of a number of symbols. ; Alphabet : A finite set of symbols. An alphabet is frequently denoted by Sigma, which is the set of letters in an alphabet.; Language : A set of words, formed by symbols in a given alphabet. May or may not be infinite. ; Kleene closure : A language may be thought of as a subset of all possible words. The set of all possible words may, in turn, be thought of as the set of all possible concatenations of strings. Formally, this set of all possible strings is called a free monoid. It is denoted as Sigma^*, and the superscript * is called the Kleene star.

Formal description

An automaton is represented by the 5-tuple langle Q, Sigma, delta, q_0, F angle, where:
*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 imes Sigma ightarrow Q.:(For non-deterministic automata, the empty string is an allowed input).
*q0 is the "start state", that is, the state in which the automaton "is" when no input has been processed yet, where q0∈ 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:Q ightarrow 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 imes Sigma^{star} ightarrow 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 angle 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, F angle is::L= { w in Sigma^{star},|;widehatdelta(q_0,w)in F}That is, the language accepted by an automaton is the set of all words "w", over the alphabet Sigma, that, when given as input to the automaton, will result in its ending in some state from F. Languages that are accepted by automata are called recognizable languages.

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.

Classes of finite automata

The following are three kinds of finite automata;Deterministic finite automata (DFA) : Each state of an automaton of this kind has a transition for every symbol in the alphabet.; Nondeterministic finite automata (NFA) : States of an automaton of this kind may or may not have a transition for each symbol in the alphabet, or can even have multiple transitions for a symbol. The automaton accepts a word if there exists at least one path from "q"0 to a state in F "labeled" with the input word. If a transition is "undefined", so that the automaton does not know how to keep on reading the input, the word is rejected.; Nondeterministic finite automata, with ε transitions (FND-ε or ε-NFA) : Besides of being able to jump to more (or none) states with any symbol, these can jump on no symbol at all. That is, if a state has transitions labeled with epsilon, then the NFA can "be" in any of the states reached by the epsilon-transitions, directly or through other states with epsilon-transitions. The set of states that can be reached by this method from a state q, is called the epsilon-closure of q.It can be shown, though, that all these automata can accept the same languages. You can always construct some DFA M' that accepts the same language as a given NFA M.

Extensions of finite automata

The family of languages accepted by the above-described automata is called the family of regular languages. More powerful automata can accept more complicated languages. Such automata include:; Pushdown automata (PDA) : Such machines are identical to DFAs (or NFAs), except that they additionally carry memory in the form of a stack. The transition function delta will now also depend on the symbol(s) on top of the stack, and will specify how the stack is to be changed at each transition. Non-determinstic PDAs accept the context-free languages.; Linear Bounded Automata (LBA): An LBA is a limited Turing machine; instead of an infinite tape, the tape has an amount of space proportional to the size of the input string. LBAs accept the context-sensitive languages.; Turing machines : These are the most powerful computational machines. They possess an infinite memory in the form of a tape, and a head which can read and change the tape, and move in either direction along the tape. Turing machines are equivalent to algorithms, and are the theoretical basis for modern computers. Turing machines decide/accepts recursive languages and recognize the recursively enumerable languages.

External links

* [http://www.versiontracker.com/dyn/moreinfo/win/35508 Visual Automata Simulator]
* [http://www.jflap.org JFLAP]
* [http://www.brics.dk/automaton dk.brics.automaton]
* [http://www.augeas.net/libfa/index.html libfa]
* [http://www.ucse.edu.ar/fma/sepa/ Proyecto SEPa (in Spanish)]
* [http://www.swisseduc.ch/informatik/exorciser/index.html Exorciser (in German)]

References

* John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - "Introduction to Automata Theory, Languages, and Computation (2nd Edition)"
* 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.
*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… …   Universalium

  • automata theory — automatų teorija statusas T sritis automatika atitikmenys: angl. automata theory vok. Automatentheorie, f rus. теория автоматов, f pranc. théorie des automates, f …   Automatikos terminų žodynas

  • Introduction to Automata Theory, Languages, and Computation —   …   Wikipedia

  • Automata-based programming — is a programming paradigm in which the program or its part is thought of as a model of a finite state machine or any other (often more complicated) formal automata (see automata theory). Sometimes a potentially infinite set of possible states is… …   Wikipedia

  • Autómata finito determinista — que reconoce el lenguaje regular conformado exclusivamente por las cadenas con un número par de ceros y un número par de unos …   Wikipedia Español

  • Automata — may refer to * Automata theory, in theoretical computer science, the study of abstract machines * The plural form of Automaton, a self operating machine. * Cellular Automata, a model of computation that is the basic design behind a broad class of …   Wikipedia

  • Theory of computation — In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata… …   Wikipedia

  • Autómata finito — Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de… …   Wikipedia Español

  • theory — /thee euh ree, thear ee/, n., pl. theories. 1. a coherent group of general propositions used as principles of explanation for a class of phenomena: Einstein s theory of relativity. 2. a proposed explanation whose status is still conjectural, in… …   Universalium

  • Autómata celular — Saltar a navegación, búsqueda Animación del juego de la vida de Conway, un autómata celular. Un autómata celula …   Wikipedia Español

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”