Crash Course on Regular Languages
Michel Rigo · 2014
This chapter provides a summary of some basic results about finite automata and regular languages. It talks about the adjacency matrix, and develop a theory of the minimal automaton. The so-called pumping lemma is a classical result that is typically used to prove that some language is not regular. Its proof relies on the pigeonhole principle: any sufficiently long path goes through the same state twice. Infinitely many DFAs accept a given infinite regular language. Among all these automata, we seek an automaton having a minimal number of states. There exist important relations between a DFA and the minimal automaton accepting the same language. These relations are expressed by morphisms of automata. The chapter considers a few operations that given any regular language, and extracts a sublanguage that is again regular. It concludes with a discussion on polynomial regular languages.