ABSTRACT
Chapters 2 to 4 have presented us with an array of languages that we can show to be recognisable. At the same time, the Pumping Lemma has provided us with a tool for showing that specific languages are not recognisable. It is clearly time to find a characterisation of recognisable languages. This is exactly what Kleene’s theorem does. The characterisation is in terms of regular expressions. Such expressions form a notation for describing languages in terms of finite languages, union, product, and Kleene star; it was informally introduced in Section 1.3. I give two different proofs of Kleene’s theorem: in Section 5.2, I prove the bare fact that a language is recognisable if and only if it is regular; in Section 5.3, I describe two algorithms: one shows how to construct an eautomaton from a regular expression, and the other shows how to construct a regular expression from an automaton. These two algorithms together give a constructive proof of Kleene’s theorem. In the last section, I describe an algebraic method for constructing a regular expression from an automaton that involves solving language equations.
