Automata Theory
Automata theory is a subject matter that studies properties of various types of automata. For example, the following questions are studied about a given type of automata.
- Which class of formal languages is recognizable by some type of automata? (Recognizable languages)
- Are certain automata closed under union, intersection, or complementation of formal languages? (Closure properties)
- How much is a type of automata expressive in terms of recognizing class of formal languages? And, their relative expressive power? (Language Hierarchy)
Automata theory also studies if there exist any effective algorithm or not to solve problems similar to the following list.
- Does an automaton accept any input word? (emptiness checking)
- Is it possible to transform a given non-deterministic automaton into deterministic automaton without changing the recognizable language? (Determinization)
- For a given formal language, what is the smallest automaton that recognizes it? (Minimization).
Read more about this topic: Automata Theory
Famous quotes containing the word theory:
“[Anarchism] is the philosophy of the sovereignty of the individual. It is the theory of social harmony. It is the great, surging, living truth that is reconstructing the world, and that will usher in the Dawn.”
—Emma Goldman (1869–1940)
Related Phrases
Related Words