Automata Theory

Information about Automata Theory

“Automata” redirects here. For a self-operating machine, see Automaton.

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.

Basic description

An automaton is a mathematical model for a finite state machine (FSM). An 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-accept 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.

Vocabulary

An automata is always anchored on the basic concepts of symbols, words, alphabets and strings. 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 $\text{[math]}$ , 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 $\text{[math]}$ , and the superscript * is called the Kleene star

Formal description

An automaton is represented by the 5-tuple $\text{[math]}$ , 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

: $\text{[math]}$

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

q₀ is the start state, that is, the state in which the automaton is when no input has been processed yet (Obviously, q₀∈ Q).
F is a set of states of Q (i.e. F⊆Q), called accept states.

Given an input letter $\text{[math]}$ , one may write the transition function as $\text{[math]}$ , using the simple trick of currying, that is, writing $\text{[math]}$ for all $\text{[math]}$ . This way, the transition function can be seen in simpler terms: its 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 $\text{[math]}$ , $\text{[math]}$ , 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 $\text{[math]}$ , one may define a new function $\text{[math]}$ , by insisting that $\text{[math]}$ , where $\text{[math]}$ denotes function composition. Clearly, this process can be recursively continued, and so one has a recursive definition of a function $\text{[math]}$ that is defined for all words $\text{[math]}$ , so that one has a map

$\text{[math]}$

The construction can also be reversed: given a $\text{[math]}$ , one can reconstruct a $\text{[math]}$ , and so the two descriptions are equivalent.

The triple $\text{[math]}$ 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 $\text{[math]}$ accepted by a deterministic finite automaton $\text{[math]}$ is:

$\text{[math]}$

That is, the language accepted by an automaton is the set of all words w, over the alphabet $\text{[math]}$ , that, when given as input to the automaton, will result in its ending in some state from $\text{[math]}$ . 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 $\text{[math]}$ , the acceptance criteria are replaced by a probability, given in terms of the metric distance between the final state $\text{[math]}$ and the set $\text{[math]}$ . Certain types of probablistic 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.
DFA
; 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₀ 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.
NFA, equivalent to the DFA from the previous exemple
; 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 $\text{[math]}$ , then the NFA can be in any of the states reached by the $\text{[math]}$ -transitions, directly or through other states with $\text{[math]}$ -transitions. The set of states that can be reached by this method from a state q, is called the $\text{[math]}$ -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 $\text{[math]}$ 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 recursive languages and recognize the recursively enumerable languages.

External links

References

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.

Automata theory: formal languages and formal grammars
Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
n/a	Indexed	Indexed	Nested stack
n/a	Tree-adjoining	Mildly context-sensitive	Thread
Type-2	Context-free	Context-free	Nondeterministic pushdown
n/a	Deterministic context-free	Deterministic context-free	Deterministic pushdown
Type-3	Regular	Regular	Finite
Each category of languages or grammars is a proper subset of the category directly above it.

automaton (plural: automata) is a self-operating machine. The word is sometimes used to describe a robot, more specifically an autonomous robot. Used colloquially, it refers to a mindless follower.
..... Click the link for more information.

Theoretical computer science is the collection of topics of computer science that focuses on the more abstract, logical and mathematical aspects of computing, such as the theory of computation, analysis of algorithms and semantics of programming languages.
..... Click the link for more information.

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. Abstraction of computing processes is used in both the computer science and computer engineering disciplines and usually assumes
..... Click the link for more information.

This article is about the term formal language as it is used in mathematics, logic and computer science. For information about a mode of expression that is more disciplined or precise than everyday speech, see Register (linguistics).

..... Click the link for more information.

Automata may refer to

Automata Theory, in theoretical computer science, the study of abstract machines
The plural form of Automaton, a self-operating machine.

..... Click the link for more information.

finite state machine (FSM) or finite state automaton (plural: automata) or simply a state machine is a model of behavior composed of a finite number of states, transitions between those states, and actions.
..... Click the link for more information.

In mathematics, a transition function has several different meanings:

In topology, a transition function is a homeomorphism from one coordinate chart to another.

..... Click the link for more information.

Mealy machine is a finite state machine (and more accurately, a finite state transducer) that generates an output based on its current state and an input. This means that the state diagram will include both an input and output signal for each transition edge.
..... Click the link for more information.

..... Click the link for more information.

countable set is a set with the same cardinality (i.e., number of elements) as some subset of the set of natural numbers. The term was originated by Georg Cantor; it stems from the fact that the natural numbers are often called counting numbers.
..... Click the link for more information.

In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines.
..... Click the link for more information.

uncountable set is an infinite set which is too big to be countable. The uncountability of a set is closely related to its cardinal number; a set is uncountable if its cardinal number is larger than that of the natural numbers.
..... Click the link for more information.

In mathematics, complex projective space, P(Cⁿ⁺¹), P_n(C) or CPⁿ, is the projective space of (complex) lines in Cⁿ⁺¹.
..... Click the link for more information.

For a general, non-technical overview of the subject, see .

Topological spaces are mathematical structures that allow the formalization of concepts such as convergence, connectedness and continuity.
..... Click the link for more information.

In mathematics and computer science, a semiautomaton or M-act is the multiplicative operation of a monoid on a set. From an algebraic point of view, it is very nearly identical to the concept of an action of a group.
..... Click the link for more information.

Probability is the likelihood that something is the case or will happen. Probability theory is used extensively in areas such as statistics, mathematics, science and philosophy to draw conclusions about the likelihood of potential events and the underlying mechanics of
..... Click the link for more information.

In mathematics, a metric space is a set where a notion of distance (called a metric) between elements of the set is defined.

The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space.
..... Click the link for more information.

Symbols are objects, characters, or other concrete representations of ideas, concepts, or other abstractions. For example, in the United States, Canada and Great Britain, a red octagon is a symbol for the traffic sign meaning "STOP".
..... Click the link for more information.

Concatenation is a standard operation in computer programming languages (a subset of formal language theory). It is the operation of joining two character strings end to end. For example, the strings "foo" and "bar" may be concatenated to give "foobar".
..... Click the link for more information.

In computer science, an alphabet is a finite set of characters or digits. The most common alphabet is {0,1}, the binary alphabet. A finite string is a finite sequence of characters from an alphabet; for instance a binary string is a string drawn from the alphabet {0,1}.
..... Click the link for more information.

SET may stand for:

Sanlih Entertainment Television, a television channel in Taiwan
Secure electronic transaction, a protocol used for credit card processing,

..... Click the link for more information.

In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*.
..... Click the link for more information.

In abstract algebra, the free monoid on a set A is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from A, with the binary operation of concatenation. It is usually denoted .
..... Click the link for more information.

For the musical term, see .

In mathematics, a tuple is a finite sequence (also known as an "ordered list") of objects, each of a specified type. A tuple containing n objects is known as an "n-tuple".
..... Click the link for more information.

currying, invented by Moses SchÃ¶nfinkel and Gottlob Frege, is the technique of transforming a function that takes multiple arguments into a function that takes a single argument (the other arguments having been specified by the curry).
..... Click the link for more information.

This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.

Herod_Archelaus

iPedia Free Information Center

Automata Theory

Information about Automata Theory

Basic description

Vocabulary

Formal description

Classes of finite automata

Extensions of finite automata

External links

References