Automates - Grammaires (INFO502_INFO)

Ce cours est une introduction aux fondements théoriques de l'informatique.

Les expressions régulières sont le premier sujet abordé : indispensable à l'arsenal de tout développeur, elles lui sont utiles au quotidien.
Les langages réguliers, second sujet abordé, permettent de répondre à la question de ce qui peut être exprimé ou non à l'aide des expressions régulières. Dans un troisième temps, nous étudions les automates finis (déterministes ou non) : utiles pour comprendre comment sont reconnues ou non les expressions régulières, ils permettent souvent de modéliser des systèmes complexes.
Dans un dernier temps, sont abordés les grammaires. Ces dernières seront notamment utiles en compilation (en cours de M1).

• Maitriser les expressions régulières et langages rationnels

• Maitriser les automates

• Comprendre ce qu'est une grammaire

1. Expressions régulières et Langages rationnels
2. Automates Déterministes et non-déterministes
3. Grammaires

Automates à états finis et langages réguliers, Falcone et Fernandez, 2020