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



In Theoretical Computer Science , automata theory is the study of Abstract Machine s 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 Language s 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''.


FORMAL DESCRIPTION


Definitions

Let us first define a few concepts to make our lives easier afterwards:
; Symbol : An arbitrary datum which has some meaning to or effect on the machine.
; Word : A finite String formed by the Concatenation of a number of symbols.
; Alphabet : A finite set of symbols.
; Language : A set of words, formed by symbols in a given alphabet. May or may not be infinite.
; Automaton : formally, an automaton is represented by the 5-tuple \langle Q, \Sigma, \delta, S_0, F angle, where:
  • Q is a finite 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.

:This function can be extended so that instead of taking just one symbol of the alphabet, it receives a string of symbols, and returns the state in which the automaton will stay after processing the input. This can be rewritten as
\hat\delta:Q imes \Sigma^{\star} ightarrow Q.

  • is the Kleene Closure of ∑.

  • S0 is the ''start state'', that is, the state in which the automaton ''is'' when no input has been processed yet (Obviously, S0∈ Q).

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

    • With all this, we can now say that the language L accepted by a DFA automaton (see below. The definition of δ is a little more complex for NFA's)M=\langle Q, \Sigma, \delta, S_0, F angle is: