Automates, Langages et Applications - TD 2
Automates, Langages et Applications - TD 2
Automates, Programming, Computer Science · exam
Voir tous les documents en programmationTous les travaux dirigés (TD) en programmation
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente un TD corrigé en Automates, Langages et Applications, destiné à tester la compréhension et la capacité à construire des automates déterministes, à manipuler des langages formels, et à raisonner sur leurs propriétés.
Cet exercice aborde la construction d'automates déterministes pour différents langages réguliers sur un alphabet binaire.
Solution détaillée :
On construit un automate qui mémorise les derniers symboles lus afin de détecter la fin "00".
Réponse : un automate à trois états q0, q1, q2 avec q2 final.
On suit la longueur de la séquence consécutive de 0 :
Transitions :
Réponse : automate à quatre états q0 à q3 avec q3 final.
Il faut mémoriser les deux derniers symboles lus :
Réponse : un automate mémorisant les deux derniers symboles avec états finaux correspondant à l’avant-dernier symbole égal à 1.
On suit la longueur des séquences consécutives de 0 et de 1 :
Réponse : automate avec états codant la longueur actuelle de la séquence consécutive pour 0 et 1, acceptant si jamais on dépasse pas 2.
Chaque état représente la congruence modulo 5 de la valeur binaire lue :
Si x ≡ b [5], alors :
x0 ≡ 2b [5]
x1 ≡ 2b + 1 [5]
L’automate commence dans l’état correspondant à la lecture du premier symbole 1 (car le mot doit commencer par 1), puis met à jour l’état selon la formule ci-dessus.
L’état final est celui correspondant à la congruence 0 modulo 5.
Réponse : automate à 5 états représentant les classes modulo 5, avec transitions définies par x0 ≡ 2b [5] et x1 ≡ 2b + 1 [5], état initial correspondant au premier 1 lu, état final celui de congruence 0.
La complémentation d'un automate déterministe nécessite qu'il soit préalablement complet.
L’automate suivant reconnaît les mots contenant "ab" :
Transitions :
Pour reconnaître les mots ne contenant pas "ab", il suffit de prendre le complémentaire de cet automate. Cela revient à inverser les états finaux et non finaux.
Réponse : Oui, on peut construire facilement l’automate complémentaire en inversant les états finaux et non finaux. Cette méthode générale consiste à construire un automate complet puis à inverser les états finaux pour obtenir le complémentaire.
On construit un automate qui commence par lire un "c" (sinon rejet). Ensuite, on suit la détection de "ab" comme précédemment.
Transitions :
Pour construire l’automate complémentaire (mots ne contenant pas "ab" ou ne commençant pas par "c"), il ne suffit pas d’inverser les états finaux car les mots ne commençant pas par "c" ne sont pas reconnus (pas de transitions depuis l’état initial pour "a" ou "b").
Il faut d’abord compléter l’automate en ajoutant un puits avec toutes les transitions manquantes, puis prendre le complémentaire.
Réponse : La méthode précédente ne suffit pas. Il faut d’abord compléter l’automate (le rendre complet) en ajoutant un puits, puis inverser les états finaux pour obtenir le complémentaire.
Cet exercice utilise un produit d'états pour suivre simultanément deux critères de parité.
Solution :
On considère les parités du nombre de a et de b lus :
L’état initial est pp (aucun a ni b lu, donc pair). L’état final est aussi pp.
Réponse : automate à 4 états (pp, pi, ip, ii) avec transitions inversant la parité correspondante, état initial et final pp.
L'analyse des changements d'états permet d'identifier la propriété du langage reconnu.
Solution :
L’automate compte la parité du nombre de b lus :
Les transitions sur a ne changent pas d’état, celles sur b changent d’état.
Réponse : Le langage reconnu est l’ensemble des mots contenant un nombre impair de b.
Tout langage fini peut être représenté sous forme d'un arbre de préfixes.
Solution :
Soit L = {01, 110, 111, 11, 00} un exemple de langage fini.
On construit un automate en forme d’arbre n-aire où chaque chemin correspond à un mot de L :
Ainsi, l’automate accepte exactement les mots de L.
Réponse : Tout langage fini est reconnaissable car on peut construire un automate en forme d’arbre reconnaissant exactement les mots du langage.
La preuve formelle de correction de l'automate s'effectue par récurrence sur la longueur du mot.
Solution :
Définissons les états :
On montre par récurrence sur la longueur du mot x :
Exemple de raisonnement :
Réponse : L’automate reconnaît exactement les mots respectant la contrainte d’équilibre et de différence maximale d’un entre le nombre de 0 et de 1 dans chaque préfixe.
La modélisation d'un système mécanique nécessite de coder la configuration interne et l'historique dans l'ensemble des états.
Solution :
Chaque état est caractérisé par :
Les états sont donc numérotés de 0 à 7 selon la position des leviers, doublés selon la sortie précédente (C ou D).
Les transitions modélisent le passage de la bille et le changement d’orientation des leviers.
Seuls les états où la dernière bille est sortie en D sont finaux.
Réponse : L’automate est défini par les états codant la position des leviers et la sortie précédente, avec transitions modélisant le passage de la bille et le changement d’orientation, et états finaux ceux où la dernière bille sort en D.
Ce TD récompense :
Les erreurs pénalisées sont :