Automata theory

related topics
{math, number, function}
{language, word, form}
{system, computer, user}
{math, energy, light}
{group, member, jewish}

In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these abstract machines. These abstract machines are called automata.

The figure at right illustrates a finite state machine, 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, as the automata are often classified by the class of formal languages they are able to recognize. An automaton can be a finite representation of a formal language that may be an infinite set.

Automata play a major role in compiler design and parsing.



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 or string of inputs in discrete time steps. At each time step, an automaton gets one input that is picked up from a set of symbols 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, automaton is in one of its states. At each time step when the automaton reads a symbol, it jumps or transits to next state depending on its current state and on the symbol currently read. This function in terms of the current state and input symbol is called transition function. The automaton reads the input word one symbol after another in the sequence 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 recognized by the automaton.

Full article ▸

related documents
Golden ratio base
Least common multiple
Borel algebra
Special linear group
Operator overloading
Cotangent space
Linear subspace
Column space
Monotone convergence theorem
Theory of computation
Product topology
Spectrum of a ring
Generating trigonometric tables
Mean value theorem
De Morgan's laws
Associative algebra
Cauchy-Riemann equations
Measure (mathematics)
1 (number)
Isomorphism theorem
Stirling's approximation
Differential topology
Sylow theorems
Tree (data structure)
Knight's tour