Difference between revisions of "Automata theory"

Revision as of 06:13, 23 March 2016

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them.

Description

It is a theory in theoretical computer science, under discrete mathematics.

Automata comes from the Greek word αὐτόματα meaning "self-acting".

The finite state machine is a well-known variety of automaton.

• This automaton consists of states, and transitions.
• 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 languages they are able to recognize.

Fields

Automata play a major role in:

• Theory of computation
• Compiler design
• Artificial intelligence
• Parsing
• Formal verification

See also

• Abstract machine
• Algorithm
• Analysis of algorithms
• Artificial intelligence
• Automaton
• Compiler
• Computation
• Computational problem
• Computer science
• Finite-state machine
• State (computer science)
• Theory of computation

External links

• Automata theory @ Wikipedia