Automata theory

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

, automata theory is the study of abstract machine

Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...

s (or more appropriately, abstract 'mathematical' machines or systems) and the computational problems that can be solved using these machines. These abstract machines are called automata. Automata comes from the Greek word αὐτόματα meaning "self-acting".

The figure at right illustrates a finite state machine

Finite state machine

A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...

, which is one well-known variety of automaton. This automaton consists of states (represented in the figure by circles), and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function (which takes the current state and the recent symbol as its inputs).

Automata theory is also closely related to formal language theory.
An automaton is a finite representation of a formal language that may be an infinite set.
Automata are often classified by the class of formal language

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

s they are able to recognize.

Automata play a major role in theory of computation

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...

, compiler design and parsing

Parsing

In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...

Automata

Following is an introductory definition of one type of automata, which attempts to help one grasp the essential concepts involved in automata theory.

Informal description

An automaton is supposed to run on some given sequence of inputs in discrete time steps. At each time step, an automaton gets one input that is picked up from a set of symbols
Symbol (formal)
For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...

or letters, which is called an alphabet. At any time, the symbols so far fed to the automaton as input form a finite sequence of symbols, which is called a word. An automaton contains a finite set of states. At each instance in time of some run, the automaton is in one of its states. At each time step when the automaton reads a symbol, it jumps or transits to a next state that is decided by a function that takes current state and the symbol currently read as parameters. This function is called transition function. The automaton reads the symbols of the input word one after another and transits from state to state according to the transition function, until the word is read completely. Once the input word has been read, the automaton is said to have been stopped and the state at which automaton has stopped is called final state. Depending on the final state, it's said that the automaton either accepts or rejects an input word. There is a subset of states of the automaton, which is defined as the set of accepting states. If the final state is an accepting state, then the automaton accepts the word. Otherwise, the word is rejected. The set of all the words accepted by an automaton is called the language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

recognized by the automaton.

In short, an automaton is a mathematical object that takes a word as input and decides either to accept it or reject it. Since all computational problems are reducible into the accept/reject question on words (all problem instances can be represented in a finite length of symbols),
automata theory plays a crucial role in computational theory.

Formal definition

Automaton

An automaton is represented formally by a 5-tuple ⟨Q,Σ,δ,q₀,A⟩, where:

Q is a finite set of states.
Σ is a finite set of symbol
Symbol
A symbol is something which represents an idea, a physical entity or a process but is distinct from it. The purpose of a symbol is to communicate meaning. For example, a red octagon may be a symbol for "STOP". On a map, a picture of a tent might represent a campsite. Numerals are symbols for...

s, called the alphabet of the automaton.
δ is the transition function, that is, δ: Q × Σ → Q.
q₀ is the start state, that is, the state of the automaton before any input has been processed, where q₀∈ Q.
A is a set of states of Q (i.e. A⊆Q) called accept states.

Input word

An automaton reads a finite string of symbols a₁,a₂,...., a_n , where a_i ∈ Σ, which is called an input word. The set of all words is denoted by Σ*.

Run

A run of the automaton on an input word w = a₁,a₂,...., a_n ∈ Σ*, is a sequence of states q₀,q₁,q₂,...., q_n, where q_i ∈ Q such that q₀ is the start state and q_i = δ(q_i-1,a_i) for 0 < i ≤ n. In words, at first the automaton is at the start state q₀, and then the automaton reads symbols of the input word in sequence. When the automaton reads symbol a_i it jumps to state q_i = δ(q_i-1,a_i). q_n is said to be the final state of the run.

Accepting word

A word w ∈ Σ* is accepted by the automaton if q_n ∈ A.

Recognized language

An automaton can recognize a formal language

Formal language

. The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted by the automaton.

Recognizable languages

The recognizable language

Recognizable language

In mathematics and computer science, a recognizable language is a formal language that is recognized by a finite state machine. Equivalently, a recognizable language is one for which the family of quotients for the syntactic relation is finite.-Definition:...

s are the set of languages that are recognized by some automaton. For the above definition of automata the recognizable languages are regular languages. For different definitions of automata, the recognizable languages are different.

Variant definitions of automata

Automata are defined to study useful machines under mathematical formalism. So, the definition of an automaton is open to variations according to the "real world machine", which we want to model using the automaton. People have studied many variations of automata. The most standard variant, which is described above, is called a deterministic finite automaton. The following are some popular variations in the definition of different components of automata.

Input

Finite input: An automaton that accepts only finite sequence of symbols. The above introductory definition only encompasses finite words.
Infinite input: An automaton that accepts infinite words (ω-words
Omega language
An ω-language is a set of infinite-length sequences of symbols.-Formal definition:Let Σ be a set of symbols . Following the standard definition from formal language theory, Σ* is the set of all finite words over Σ. Every finite word has a length, which is, obviously, a natural number...

). Such automata are called ω-automata.
Tree word input: The input may be a tree of symbols instead of sequence of symbols. In this case after reading each symbol, the automaton reads all the successor symbols in the input tree. It is said that the automaton makes one copy of itself for each successor and each such copy starts running on one of the successor symbol from the state according to the transition relation of the automaton. Such an automaton is called tree automaton
Tree automaton
A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines.The following article deals with branching tree automata, which correspond to regular languages of trees...

.
Infinite tree input : The two extensions above can be combined, so the automaton reads a tree structure with (in)finite branches. Such an automaton is called infinite tree automaton
Infinite tree automaton
In computer science and mathematical logic, an infinite tree automaton is a state machine that deals with infinite tree structure. It can be viewed as an extension from a finite tree automaton, which accepts only finite tree structures...

States

Finite states: An automaton that contains only a finite number of states. The above introductory definition describes automata with finite numbers of states.
Infinite states: An automaton that may not have a finite number of states, or even a countable number of states. For example, the quantum finite automaton or topological automaton has uncountable infinity of states.
Stack memory: An automaton may also contain some extra memory in the form of a stack in which symbols can be pushed and popped. This kind of automaton is called a pushdown automaton
Pushdown automaton
In automata theory, a pushdown automaton is a finite automaton that can make use of a stack containing data.- Operation :Pushdown automata differ from finite state machines in two ways:...

Transition function

Deterministic: For a given current state and an input symbol, if an automaton can only jump to one and only one state then it is a deterministic automaton
Deterministic automaton
Deterministic automaton is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence....

.
Nondeterministic: An automaton that, after reading an input symbol, may jump into any of a number of states, as licensed by its transition relation. Notice that the term transition function is replaced by transition relation: The automaton non-deterministically decides to jump into one of the allowed choices. Such automata are called nondeterministic automata.
Alternation: This idea is quite similar to tree automaton, but orthogonal. The automaton may run its multiple copies on the same next read symbol. Such automata are called alternating automata. Acceptance condition must satisfy all runs of such copies to accept the input.

Acceptance condition

Acceptance of finite words: Same as described in the informal definition above.
Acceptance of infinite words: an omega automaton cannot have final states, as infinite words never terminate. Rather, acceptance of the word is decided by looking at the infinite sequence of visited states during the run.
Probabilistic acceptance: An automaton need not strictly accept or reject an input. It may accept the input with some probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...

between zero and one. For example, quantum finite automaton, geometric automaton and metric automaton have probabilistic acceptance.

Different combinations of the above variations produce many classes of automaton.

Automata theory is a subject matter that studies properties of various types of automata. For example, the following questions are studied about a given type of automata.

Which class of formal languages is recognizable by some type of automata? (Recognizable languages)
Are certain automata closed under union, intersection, or complementation of formal languages? (Closure properties)
How much is a type of automata expressive in terms of recognizing class of formal languages? And, their relative expressive power? (Language Hierarchy)

Automata theory also studies if there exist any effective algorithm or not to solve problems similar to the following list.

Does an automaton accept any input word? (emptiness checking)
Is it possible to transform a given non-deterministic automaton into deterministic automaton without changing the recognizable language? (Determinization)
For a given formal language, what is the smallest automaton that recognizes it? (Minimization
Dfa minimization
In computer science, more specifically in the branch of automata theory, DFA minimization is the task of transforming a given deterministic finite automaton into an equivalent DFA that has minimum number of states. Here, two DFAs are called equivalent if they describe the same regular language...

).

Classes of automata

The following is an incomplete list of types of automata.

Automata	Recognizable language
Deterministic finite automata (DFA) Deterministic finite state machine In the theory of computation and automata theory, a deterministic finite state machine—also known as deterministic finite automaton —is a finite state machine accepting finite strings of symbols. For each state, there is a transition arrow leading out to a next state for each symbol...	regular language Regular language In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression.... s
Nondeterministic finite automata (NFA) Nondeterministic finite state machine In the automata theory, a nondeterministic finite state machine or nondeterministic finite automaton is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states...	regular languages
Nondeterministic finite automata with ε-transitions (FND-ε or ε-NFA)	regular languages
Pushdown automata (PDA) Pushdown automaton In automata theory, a pushdown automaton is a finite automaton that can make use of a stack containing data.- Operation :Pushdown automata differ from finite state machines in two ways:...	context-free languages
Linear bounded automata (LBA)	context-sensitive language Context-sensitive language In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...
Turing machine Turing machine A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a... s	recursively enumerable language Recursively enumerable language In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages... s
Timed automata
Deterministic Büchi automata Büchi automaton In computer science and automata theory, a Büchi automaton is a type of ω-automaton, which extends a finite automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton that visits one of the final states infinitely often. Büchi automata recognize the...	ω-limit languages
Nondeterministic Büchi automata	ω-regular languages Omega-regular language The ω-regular languages are a class of ω-languages which generalize the definition of regular languages to infinite words. Büchi showed in 1962 that ω-regular languages are precisely the ones definable in a particular monadic second-order logic called S1S.- Formal definition :An...
Nondeterministic/Deterministic Rabin automata	ω-regular languages
Nondeterministic/Deterministic Streett automata	ω-regular languages
Nondeterministic/Deterministic parity automata	ω-regular languages
Nondeterministic/Deterministic Muller automata Muller automaton In automata theory, a Muller automaton is a type of an ω-automaton.The acceptance condition separates a Muller automomaton from other ω-automata....	ω-regular languages

Discrete, continuous, and hybrid automata

Normally automata theory describes the states of abstract machines but there are analog automata or continuous automata or hybrid discrete-continuous automata

Hybrid automaton

In automata theory, a hybrid automaton is a mathematical model for precisely describing systems in which digital computational processes interact with analog physical processes. A hybrid automaton is a finite state machine with a finite set of continuous variables whose values are described by a...

, which use analog data, continuous time, or both.

Applications

Each model in automata theory plays an imporant roles in several applied areas. Finite automata are used in text processing, compilers, and hardware design. Context-free grammar

Context-free grammar

In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....

(CFGs) are used in programming languages and artificial intelligence. Originally, CFGs were used in the study of the human languages. Cellular automata are used in the field of biology, the most common example being John Conway

John Horton Conway

John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...

's Game of Life

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

. Some other examples which could be explained using automata theory in biology include mollusk and pine cones growth and pigmentation patterns. Going further, a theory suggesting that the whole universe is computed by some sort of a discrete automaton, is advocated by some scientists. The idea originated in the work of Konrad Zuse

Konrad Zuse

Konrad Zuse was a German civil engineer and computer pioneer. His greatest achievement was the world's first functional program-controlled Turing-complete computer, the Z3, which became operational in May 1941....

, and was popularized in America by Edward Fredkin

Edward Fredkin

Edward Fredkin is an early pioneer of digital physics. In recent work, he uses the term digital philosophy . His primary contributions include his work on reversible computing and cellular automata...

Connection to Category theory

One can define several distinct categories

Category (mathematics)

In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...

of automata following the automata classification into different types described in the previous section. The mathematical category of deterministic automata, sequential machines or sequential automata, and Turing machines with automata homomorphisms defining the arrows between automata is a Cartesian closed category

Cartesian closed category

In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...

, it has both categorical limits and colimits. An automata homomorphism maps a quintuple of an automaton A_i onto the quintuple of another automaton
A_j. Automata homomorphisms can also be considered as automata transformations or as semigroup homomorphisms, when the state space,S, of the automaton is defined as a semigroup S_g. Monoid

Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...

s are also considered as a suitable setting for automata in monoidal categories

Monoidal category

In mathematics, a monoidal category is a category C equipped with a bifunctorwhich is associative, up to a natural isomorphism, and an object I which is both a left and right identity for ⊗, again up to a natural isomorphism...

.

Categories of variable automata
One could also define a variable automaton, in in the sense of Norbert Wiener in his book on "Human Use of Human Beings" via the endomorphisms A_i-->A_i. Then, one can show that such variable automata homomorphisms form a mathematical group. In the case of non-deterministic, or other complex kinds of automata, the latter set of endomorphisms may become, however, a variable automaton groupoid
Groupoid
In mathematics, especially in category theory and homotopy theory, a groupoid generalises the notion of group in several equivalent ways. A groupoid can be seen as a:...

. Therefore, in the most general case, categories of variable automata of any kind are categories of groupoids or groupoid categories. Moreover, the category of reversible automata is then a
2-category

2-category

In category theory, a 2-category is a category with "morphisms between morphisms"; that is, where each hom set itself carries the structure of a category...

, and also a subcategory of the 2-category of groupoids, or the groupoid category.

External links

Visual Automata Simulator, A tool for simulating, visualizing and transforming finite state automata and Turing Machines, by Jean Bovet
JFLAP
dk.brics.automaton
libfa
Proyecto SEPa (in Spanish)
Exorciser (in German)
Automata Made it on Java, with the Sources so you can see

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.