ABSTRACT
Kleene’s Theorem was the first major result on finite automata. The second deep theorem on finite automata, due to Schiitzenberger, is the subject of this chapter. The set of recognisable languages is closed under union, product, and Kleene star, and it is also closed under all the other Boolean operations. Suppose we retain all the other operations but discard Kleene star, what can we say about the languages that can then be described? Such languages are said to be ‘star-free.’ The goal of this chapter is to characterise star-free languages, and the main tool we shall use to obtain our characterisation will be the syntactic monoid of the language. Our characterisation provides conclusive proof of the importance of the syntactic monoid in studying recognisable languages.
