TD Série 1: Automates non déterministes et expressions régulières – Théorie des langages et automates

Ce document constitue la première série d'exercices (TD) dédiée à l'étude des automates finis non déterministes et des expressions régulières, thème central de la théorie des langages formels. Il comporte six exercices progressifs qui abordent la construction d'automates non déterministes à partir d'expressions régulières données, la déterminisation d'automates, la description de langages par des expressions régulières, ainsi que la fermeture des langages rationnels sous diverses opérations (concaténation, union, étoile). L'exercice 1 demande de construire un automate non déterministe acceptant des langages définis par des expressions telles que (0+1)*00, (0+1)*1(0+1)^9, ou encore le complément du langage contenant le motif 101. L'exercice 2 analyse un automate donné, vérifie l'acceptation de certaines chaînes et détermine le langage reconnu sous la forme 0*(0+1)1* + 0*(1+ε)0*11*. L'exercice 3 travaille sur les langages L2 contenant le sous‑mot 101 et LA défini par des contraintes d'égalité et de présence de symboles. Les exercices 4 à 6 portent sur la caractérisation de langages par des propriétés de longueur, de début/fin, de parité du nombre de symboles 1, et sur la manipulation d'expressions régulières provenant de figures d'automates. Chaque exercice renforce la compréhension des équivalences entre expressions régulières, automates non déterministes et déterministes, ainsi que les techniques de preuve par construction ou par récurrence. Ce TD permet à l'étudiant de maîtriser les outils fondamentaux de la théorie des langages, préparant ainsi aux examens écrits et aux projets de conception d'analyseurs lexicaux ou de vérificateurs de propriétés formelles.