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:
“It is not enough for theory to describe and analyse, it must itself be an event in the universe it describes. In order to do this theory must partake of and become the acceleration of this logic. It must tear itself from all referents and take pride only in the future. Theory must operate on time at the cost of a deliberate distortion of present reality.”
—Jean Baudrillard (b. 1929)
Related Phrases
Related Words