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:
“There is in him, hidden deep-down, a great instinctive artist, and hence the makings of an aristocrat. In his muddled way, held back by the manacles of his race and time, and his steps made uncertain by a guiding theory which too often eludes his own comprehension, he yet manages to produce works of unquestionable beauty and authority, and to interpret life in a manner that is poignant and illuminating.”
—H.L. (Henry Lewis)