Semaine du lundi 30 septembre 2024
Tout ce qui précède est susceptible de tomber, mais on pourra se focaliser sur les automates pour donner des exercices divers et variés.
Automates
- Connaître la définition d'automates, de chemin et chemin acceptant, de mot accepté et de langage accepté
- Sur de petits exemples, pouvoir donner le langage reconnu par un automate, et réciproquement, donner un automate reconnaissant un langage.
- En particulier, être à l'aise pour manipuler la fonction de transitions $\delta$ et son extension $\delta^*$ dans des exercices qui demandent de l'utiliser pour raisonner (il est conseillé de relire les démonstrations du cours qui y font appel), et être capable d'utiliser leur correspondance avec les chemins réalisables dans l'automate.
- Savoir émonder un automate, et donc savoir qu'on peut toujours se ramener à un automate émondé qui reconnaît le même langage qu'un automate donné.
- Savoir compléter un automate, et donc savoir qu'on peut toujours se ramener à un automate complet qui reconnaît le même langage qu'un automate donné.
- Savoir déterminiser un automate, et donc savoir qu'on peut toujours se ramener à un automate déterministe qui reconnaît le même langage qu'un automate donné.
- Connaître l'ordre de grandeur du coût de la déterminisation (exponentiel en la taille de l'automate) et savoir le justifier.
Les automates avec $\varepsilon$-transitions ont été vus, et on pourra les faire intervenir dans de petits exemples ou accepter des constructions qui les utilisent, mais l'algorithme d'élimination des $\varepsilon$-transitions est encore trop récent. Les résultats de stabilité (construction d'automates pour l'union, l'intersection, le complémentaire) n'ont pas été vus. Le théorème de Kleene n'a pas été vu, mais on pourra le fournir aux élèves en l'admettant si cela peut être utile dans un exercice. Le lemme de l'étoile n'a pas été vu.
