Leçon 2 sur 5
Les automates finis
Je sais construire et exécuter un automate fini, déterminiser un automate non déterministe, minimiser un automate déterministe et démontrer qu'un langage n'est pas régulier.
- 1 h 30
- 7 exercices corrigés
- QCM de 7 questions
À la fin de la leçon, vous saurez :
- Définir un automate fini déterministe et l'exécuter sur un mot à l'aide de sa table de transitions
- Construire un automate pour un langage décrit en français ou par une expression régulière
- Déterminiser un automate non déterministe par la construction des sous-ensembles
- Minimiser un automate déterministe par raffinement de partitions
- Utiliser le théorème de Kleene, les propriétés de clôture et le lemme de l'étoile
Avant de commencer : Leçon 1 (mots, langages, expressions régulières) ; Mathématiques discrètes (ensembles, relations d'équivalence, récurrence).
1Je découvre
Alpha, étudiant en L3 à l'université Gamal Abdel Nasser de Conakry, écrit une calculatrice en Python. Son programme doit d'abord reconnaître les nombres dans ce que tape l'utilisateur : « 12 » et « 3.75 » sont valides, mais « 3. », « .5 » ou « 1.2.3 » ne le sont pas. Il a écrit une suite de if imbriqués de plus de quarante lignes, et chaque nouveau cas casse un cas précédent.
Son enseignant dessine au tableau quatre cercles reliés par des flèches : « Votre programme ne doit retenir qu'une chose : où en est-il dans la lecture du nombre. Avant le premier chiffre, dans la partie entière, juste après le point, dans la partie décimale. Quatre états suffisent. »
Ce modèle, l'automate fini, est au cœur des analyseurs lexicaux des compilateurs, des protocoles réseau, des distributeurs automatiques et des moteurs d'expressions régulières.
Comment représenter un programme qui lit un mot lettre par lettre avec une mémoire finie, et quels langages peut-il reconnaître ?
La suite se lit avec votre compte Kharandi Université
La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.
Voir toutes les leçons de Théorie des langages et compilation