Automata theory

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science, under discrete mathematics (a subject of study in both mathematics and computer science). The word automata (the plural of automaton) comes from a Greek word, which means “self-acting”.

An automata is composed by automaton. The automaton can be represent by:

• Its states: the available states that the automaton can be.
• Its transitions: the transitions between states, defined by a transition function.

An automaton is formally defined by a 5-tuple (Q,Σ,δ,q0,F), where:

• Q is a finite set of states.
• Σ is a finite set of symbols, called the alphabet of the automaton.
• δ is the transition function, that is, δ: Q × Σ → Q.
• q0 is the start state, that is, the state of the automaton before any input has been processed, where q0∈ Q.
• F is a set of states of Q (i.e. F⊆Q) called accept states.

Automata theory is 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 can recognize, typically illustrated by the Chomsky hierarchy which describes the relations between various languages and kinds of formalized logic.

Related fields

Automata play a major role in:

• theory of computation
• compiler construction
• artificial intelligence
• parsing
• formal verification

Types of automaton

The following is an incomplete list of types of automata:

• Nondeterministic/Deterministic Finite state machine (FSM): regular languages
• Deterministic pushdown automaton (DPDA): deterministic context-free languages
• Pushdown automaton (PDA): context-free languages
• Linear bounded automaton (LBA): context-sensitive languages
• Turing machine: recursively enumerable languages
• Deterministic Büchi automaton: ω-limit languages
• Nondeterministic Büchi automaton: ω-regular languages
• Rabin automaton, Streett automaton, Parity automaton, Muller automaton: ω-regular languages

See also

Artificial Intelligence, Mathematical optimization

Material

• http://scanftree.com/automata/

Books

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Introduction to Automata Theory, Languages, and Computation (2nd Edition). Pearson
• Yan, Song Y. (1998). An Introduction to Formal Languages and Machine Computation. Singapore: World Scientific Publishing Co. Pte. Ltd.
• Sakarovitch, Jacques (2009). Elements of automata theory. Cambridge University Press.
• Marvin Minsky (1967). Computation : Finite and infinite machines. Princeton, N.J.: Prentice Hall.