Theory of regular languages

The second-year seminar on the theory of regular languages (THLR, théorie des langages rationnels) at EPITA Toulouse, in 2019-2020. This course draws on the seminar's original material, but I rebuilt it entirely: a new organisation, a text written out from start to finish, examples and exercises.

Seven chapters and seven exercise sheets. Chapters 1 and 2 set out the vocabulary and regular expressions; chapter 3 defines automata; chapters 4 and 5 show that expressions and automata describe the same languages (Kleene's theorem), giving the algorithms to go from one to the other. Chapters 6 and 7 explore the properties of these languages, and their limits.

Automata are drawn with consistent conventions: an incoming arrow for an initial state, a double circle for a final state.

Lecture notes

1. Words and languages : The basic vocabulary of the whole course. Alphabet, word, concatenation, prefixes and factors, language, and the operations on languages up to the Kleene star.
2. Regular expressions : Describing infinite languages finitely. Regular languages, the expressions that denote them, their rules of calculation, and what separates them from the regexes of programming languages.
3. Finite automata : A machine with finite memory that reads a word letter by letter and answers yes or no. Definitions of deterministic, nondeterministic and spontaneous-transition automata, and the vocabulary to talk about them.
4. From expressions to automata : Compiling a regular expression into a deterministic automaton, in three mechanical steps. Thompson's construction, the elimination of spontaneous transitions, determinisation by subsets.
5. From automata to expressions, Kleene's theorem : Recovering a regular expression from an automaton, by state elimination or by solving equations. We deduce that the regular languages are exactly the recognisable languages.
6. Closure properties : Which operations preserve regular languages? Transpose, prefixes, factors, subwords, complement, intersection, and the synchronised product, which makes it possible to test inclusion and equivalence.
7. Minimisation and limits : What an automaton must remember, and what it cannot remember. Residuals, the minimal automaton and Moore's algorithm; the pumping lemma, to show that a language is not regular.

Exercise sheets

1. Words and languages : Prefixes, factors and subwords, products and stars of languages, and a few identities to prove or disprove. Chapter 1.
2. Regular expressions : Reading, writing and comparing regular expressions; going from a specification in plain English to a precise expression. Chapter 2.
3. Finite automata : Reading, building, trimming, completing and running automata, deterministic or not. Chapter 3.
4. From expressions to automata : Thompson's construction, elimination of spontaneous transitions, determinisation, and the price of determinisation. Chapter 4.
5. From automata to expressions : State elimination in different orders, solving equations with Arden's lemma, and an expression for the multiples of 3 in binary. Chapter 5.
6. Closure properties : Transpose, complement, synchronised product and inclusion testing, then a few closure proofs by building automata. Chapter 6.
7. Minimisation and limits : Minimising a DFA with Moore's algorithm, computing residuals, and proving that a language is not regular. Chapter 7.