Automata Theory - Automata Theory

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).