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:
“The whole theory of modern education is radically unsound. Fortunately in England, at any rate, education produces no effect whatsoever. If it did, it would prove a serious danger to the upper classes, and probably lead to acts of violence in Grosvenor Square.”
—Oscar Wilde (1854–1900)
Related Phrases
Related Words