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.

Contents

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