LoginHome


Advanced search
Catalogs >> Computer Science >> Paris Program
Lecturer :

Pierre SENELLART
  

Teaching staff :
Antoine AMARILLI
Akim DEMAILLE
Olivier HUDRY
David MADORE
Pooran Memari
Jacques SAKAROVITCH
Pierre SENELLART
à prévoir SURVEILLANT

Level : UnderGraduate

Course Language : French

Number of hours : 12
INF105 Formal languages
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

© Télécom ParisTech 2017 - Developed by Winch Communication