Semaine du lundi 7 octobre 2024
Tout ce qui précède est susceptible de tomber. Cette fois-ci, l'intégralité du chapitre sur les automates est incluse. Précisons ce qui est concrètement ajouté :
Automates
- Savoir appliquer l'algorithme d'élimination des $\varepsilon$-transitions (en n'oubliant pas l'étape de la clôture). Sur un exercice plus théorique dans lequel on présente un automate qui peut avoir des $\varepsilon$-transitions, il faut savoir dire qu'on peut se ramener au cas où l'automate n'en possède pas.
- Savoir construire un automate qui reconnaît l'intersection des langages de deux autres automates (l'automate produit) et le complémentaire du langage d'un autre automate ; savoir le faire également pour l'union, mais c'est très facile.
- Connaître le théorème de Kleene, et les deux algorithmes (Berry-Sethi et élimination d'états) permettant de passer d'une expression régulière à un automate et réciproquement. Ces deux méthodes pour passer d'un modèle de calcul à l'autre sont les seules au programme.
- Savoir utiliser le théorème de Kleene dans un raisonnement. Le théorème est assez classique pour qu'on puisse l'utiliser sans avoir à le nommer, mais il faut être capable de parler du théorème si on le demande.
- Connaître les "nouveaux" résultats de stabilité sur les langages réguliers, obtenus par le théorème de Kleene : l'intersection et le complémentaire de langages réguliers sont réguliers.
- Connaître le lemme de l'étoile, et savoir l'utiliser avec une preuve par l'absurde pour démontrer que des langages ne sont pas réguliers. On peut directement dériver une contradiction du lemme de l'étoile, mais on peut aussi utiliser les résultats de stabilité pour construire des langages qui devraient être réguliers, alors qu'on sait très bien qu'ils ne le sont pas ; à ce titre, il FAUT connaître au minimum un langage non régulier ; celui des $a^nb^n$ est un bon candidat, mais on peut en connaître d'autres (palindromes, mots bien parenthésés).
