Jin Hyun Park / Qual Exam Prep / Automata theory

Automata theory (theory of computation)

Most theory questions on the exam are about which class a language belongs to and what operations keep it there.

The language classes, from smallest to largest

Regular ⊂ context-free ⊂ decidable ⊂ recognizable. Regular languages are what finite automata (and regular expressions) can handle; context-free languages need a pushdown automaton (a stack); decidable and recognizable languages need a Turing machine. Keep this ordering in mind, because many questions are really asking "is this language still in the same class after I do X to it?"

Closure properties

A class is closed under an operation if applying the operation to languages in the class always gives a language in the class.

Class	Union	Intersection	Concatenation	Star	Complement
Regular	yes	yes	yes	yes	yes
Context-free	yes	no	yes	yes	no
Decidable	yes	yes	yes	yes	yes
Recognizable	yes	yes	yes	yes	no

• The two "no" entries for context-free languages go together: if CFLs were closed under complement, they would be closed under intersection too, by De Morgan's law.
• Recognizable languages are not closed under complement. If both a language and its complement are recognizable, the language is actually decidable (run both recognizers in parallel; one of them must halt).

Decidability

• Every finite language is decidable: a Turing machine can simply compare the input against the finite list of members.
• Only an infinite language can be undecidable.
• The converse is not true: plenty of infinite languages are decidable. Σ* (the set of all strings) is infinite and trivially decidable.

A few facts that get tested

• Every finite language is regular (you can write a regular expression that just lists the strings).
• Every subset of a countable set is either countable or finite.

Decidable vs. recognizable languages

• A decidable (also called recursive) language has a Turing machine that always halts: it accepts strings in the language and rejects strings not in the language. It never runs forever.
• A recognizable (also called recursively enumerable) language has a Turing machine that accepts every string in the language, but on strings not in the language it may either reject or run forever. You can confirm membership, but you cannot always confirm non-membership.
• Every decidable language is recognizable, but not the other way around. The halting problem is the standard example of a language that is recognizable but not decidable.

Overview · Useful materials · Sample questions · Algorithms · Architecture · OS · Networking · Databases · AI / ML · Things to remember