Leçon 909 : Langages rationnels et automates finis. Exemples et applications.

(2019) 909
(2021) 909

Dernier rapport du Jury :

(2019 : 909 - Langages rationnels et automates finis. Exemples et applications.) Pour cette leçon très classique, il importe de ne pas oublier de donner exemples et applications,ainsi que le demande l’intitulé. $\\$ Une approche algorithmique doit être privilégiée dans la présentation des résultats classiques (déterminisation, théorème de Kleene, etc.) qui pourra utilement être illustrée par des exemples. $\\$ Le jury est naturellement amené à poser des questions telles que : « connaissez-vous un algorithme pour décider de l’égalité des langages reconnus par deux automates ? quelle est sa complexité ? » Des applications dans le domaine de l’analyse lexicale et de la compilation entrent naturellement dans le cadre de cette leçon.

(2017 : 909 - Langages rationnels et automates finis. Exemples et applications.) Pour cette leçon très classique, il importe de ne pas oublier de donner exemples et applications, ainsi que le demande l’intitulé. Une approche algorithmique doit être privilégiée dans la présentation des résultats classiques (déterminisation, théorème de Kleene, etc.) qui pourra utilement être illustrée par des exemples. Le jury pourra naturellement poser des questions telles que : connaissez-vous un algorithme pour décider de l’égalité des langages reconnus par deux automates ? quelle est sa complexité ? Des applications dans le domaine de l’analyse lexicale et de la compilation entrent naturellement dans le cadre de cette leçon.

Développements :

Plans/remarques :

2018 : Leçon 909 - Langages rationnels et automates finis. Exemples et applications.


Retours d'oraux :

Pas de retours pour cette leçon.

Références utilisées dans les versions de cette leçon :

Langages formels, Calculabilité et Complexité, Carton (utilisée dans 19 versions au total)
Mathématiques de l'informatique , Dehornoy (utilisée dans 8 versions au total)