Finite automata and applications

Finite automata can be used to model computer programs with finite memory. They enable problems to be solved at a high level of abstraction, without being encumbered by the specifics of a given language, and by concentrating on the invariants to be maintained in order to arrive at a solution. The study of this model is part of the general framework of language theory covered in modules IF203 (compilation) and IF228 (computability and complexity). The teaching covers theoretical notions (finite automata, regular languages, regular expressions, equivalence of these three formalisms, non-determinism, minimal automata, star lemma) and their use in solving concrete problems.

No

Finite automata, languages
Regular expressions, Kleene's theorem
Non-regular languages, star lemma
Grammars
Determinism, determinization algorithm
Minimal automata, minimization algorithm
Introduction to lexical analysis

Handout