Automata theory
From Wiki @ Karl Jones dot com
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.
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.
Automata play a major role in theory of computation, compiler design, artificial intelligence, parsing and formal verification.
External links
- Automata theory @ Wikipedia
