The class of regular languages is the smallest class of languages containing the finite languages that is closed under finite union, finite product and star. The definition of star-free languages follows the same pattern, with the difference that the star operation is replaced by the complement. In other words, the class of star-free languages is the smallest class of languages containing the finite languages that is closed under finite union, finite product and complement.

In this lecture, I will present some standard and less standard methods to prove that a language is regular or star-free.