Theory of Computation · topic
Closure of regular languages, decision procedures (membership, emptiness, finiteness, equivalence), Myhill-Nerode classes and the minimal DFA, the pumping lemma with the correct quantifier order and its common misuses, standard non-regular languages and fast classification of look-alikes.
Regular languages are closed under a rich family of operations: Boolean operations, concatenation, star, reverse, homomorphisms and inverse homomorphisms. They also have decidable emptiness, membership, finiteness and equivalence.
The pumping lemma for regular languages is a necessary condition that every regular language satisfies. Its main use is negative: if you can show that a language breaks the condition, the language is not regular.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
