Automata Theory Shopping
Automata 		Website Links For
Automata Theory 		 

Information About

Automata Theory
  CATEGORIES ABOUT AUTOMATA THEORY
   
automata theoryautomata theory
   
theory of computation
   
formal languages
   
formal methods
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




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.
; of letters in an alphabet.
; Language : A set of words, formed by symbols in a given alphabet. May or may not be infinite.


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 (Obviously, q0∈ Q).

  • F is a set of states of Q (i.e. F⊆Q), called accept states.


Given an input letter a\in\Sigma, one may write the transition function as \delta_a:Q ightarrow Q, using the simple trick of 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''.

  • , so that one has a map


:\widehat\delta:Q imes \Sigma^{\star} ightarrow Q.

The construction can also be reversed: given a \widehat\delta, one can reconstruct a \delta, and so the two descriptions are equivalent.

The triple \langle Q, \Sigma, \delta angle is known as a . The language L accepted by a deterministic finite automaton \langle Q, \Sigma, \delta, q_0, F angle is: