This course provides an introduction to formal language theory, introducing concepts that will be helpful in several advanced IT and network courses.
General word and language notions are first introduced, after which the formalism of regular expressions is presented, making it possible to describe a major class of languages: rational languages. Finite-state automata (FSA) are then introduced, as are the main algorithms used to manipulate them (determinisation, minimisation etc.). It is then shown that these machines make it possible to recognise rational languages. The notion of formal grammar and its use to describe languages is then introduced. Two subclasses of grammar are studied: regular grammars, whose equivalence to regular expressions will be noted, then the context-free grammars. This in part of the study of Chomsky's hierarchy. A brief introduction to context-free parsing is given. Finally, the notion of (semi-)decidability of a language is introduced and discussed.
Last Modification : Thursday 27 August 2015