Automates, Langages et Applications - TD 2

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.

Exercice 1 : Automates déterministes sur l’alphabet {0, 1}

Cet exercice aborde la construction d'automates déterministes pour différents langages réguliers sur un alphabet binaire.

• Les mots se terminant par 00 ;
• Les mots ayant au moins 3 zéros consécutifs ;
• Les mots dont l’avant-dernier symbole est un 1 ;
• Les mots contenant au plus deux 0 consécutifs et au plus deux 1 consécutifs ;
• Les mots commençant par 1 et, interprétés comme des entiers en binaire, congrus à 0 modulo 5.

Solution détaillée :

1. Mots se terminant par 00

On construit un automate qui mémorise les derniers symboles lus afin de détecter la fin "00".

• État initial q₀ : aucun symbole lu ou pas encore de 0 en fin.
• En lisant un 0, on passe à q₁ (dernier symbole lu est 0).
• En lisant un 1, on revient à q₀ (car la fin ne peut pas être "00").
• En q₁, si on lit un 0, on passe à q₂ (fin "00" détectée).
• En q₁, si on lit un 1, on revient à q₀.
• q₂ est un état final car le mot se termine par "00".

Réponse : un automate à trois états q₀, q₁, q₂ avec q₂ final.

2. Mots ayant au moins 3 zéros consécutifs

On suit la longueur de la séquence consécutive de 0 :

• q₀ : aucun zéro consécutif en cours.
• q₁ : un zéro consécutif lu.
• q₂ : deux zéros consécutifs lus.
• q₃ : au moins trois zéros consécutifs (état final).

Transitions :

• De q₀, lire 0 → q₁, lire 1 → q₀.
• De q₁, lire 0 → q₂, lire 1 → q₀.
• De q₂, lire 0 → q₃, lire 1 → q₀.
• De q₃, lire 0 ou 1 → q₃ (reste dans l'état final).

Réponse : automate à quatre états q₀ à q₃ avec q₃ final.

3. Mots dont l’avant-dernier symbole est un 1

Il faut mémoriser les deux derniers symboles lus :

• On peut définir des états représentant les derniers symboles lus.
• Par exemple, q₀ état initial (pas encore lu), q₁ dernier symbole 0, q₂ dernier symbole 1, q₃ derniers symboles "10", q₄ derniers symboles "11", etc.
• L’état final correspond aux mots dont l’avant-dernier symbole est 1, donc les états où le symbole avant le dernier est 1.

Réponse : un automate mémorisant les deux derniers symboles avec états finaux correspondant à l’avant-dernier symbole égal à 1.

4. Mots contenant au plus deux 0 consécutifs et au plus deux 1 consécutifs

On suit la longueur des séquences consécutives de 0 et de 1 :

• États représentant le nombre de 0 ou 1 consécutifs lus (0, 1, 2).
• Si on lit un symbole différent, on revient à 1 pour ce symbole.
• Si on lit un troisième symbole identique consécutif, on passe à un état de rejet (non final).

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.

5. Mots commençant par 1 et congrus à 0 modulo 5

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.

Exercice 2 : Automates sur l’alphabet Σ = {a, b} puis Σ = {a, b, c}

La complémentation d'un automate déterministe nécessite qu'il soit préalablement complet.

1. Mots sur Σ = {a, b}

L’automate suivant reconnaît les mots contenant "ab" :

• q₀ : état initial, aucun symbole "a" détecté.
• q₁ : on a lu un "a" et on attend un "b".
• q₂ : on a détecté "ab" (état final).

Transitions :

• De q₀, lire "a" → q₁, lire "b" → q₀.
• De q₁, lire "b" → q₂, lire "a" → q₁.
• De q₂, lire "a" ou "b" → q₂ (état final).

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.

2. Extension à Σ = {a, b, c}

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 :

• État initial q₀ : on attend un "c". Si on lit "c", on passe à q₁, sinon on va vers un puits (état de rejet).
• q₁, q₂, q₃ suivent la détection de "ab" comme dans l’exercice précédent.

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.

Exercice 3 : Automate reconnaissant les mots avec un nombre pair de a et un nombre pair de b

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 :

• Chaque état est codé par un couple (parité de a, parité de b), où chaque parité est soit p (pair) soit i (impair).
• Les états sont donc : pp, pi, ip, ii.
• Transitions :

• Lire un "a" inverse la parité de a, la parité de b reste la même.
• Lire un "b" inverse la parité de b, la parité de a reste la même.

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.

Exercice 4 : Langage reconnu par un automate donné

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 :

• État 0 : nombre pair de b.
• État 1 : nombre impair de b.

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.

Exercice 5 : Montrer qu’un langage fini est reconnaissable

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 :

• Chaque état correspond à un préfixe d’un mot de L.
• Les états finaux correspondent aux mots complets 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.

Exercice 6 : Automate reconnaissant les mots avec autant de 0 que de 1 et contraintes sur les préfixes

La preuve formelle de correction de l'automate s'effectue par récurrence sur la longueur du mot.

Solution :

Définissons les états :

• q₀ : mot correct avec autant de 0 que de 1.
• q₁ : mot correct avec un 0 de plus que de 1.
• q₂ : mot correct avec un 1 de plus que de 0.
• q₃ : mot incorrect (préfixe ne respectant pas la contrainte).

On montre par récurrence sur la longueur du mot x :

• Si δ(q₀, x) = q₀ alors x est correct et a autant de 0 que de 1.
• Si δ(q₀, x) = q₁ alors x est correct et a un 0 de plus que de 1.
• Si δ(q₀, x) = q₂ alors x est correct et a un 1 de plus que de 0.
• Si δ(q₀, x) = q₃ alors x n’est pas correct.

Exemple de raisonnement :

• Pour |x|=0, x=ε, δ(q₀, ε)=q₀, ε a autant de 0 que de 1.
• Si y = x0 et δ(q₀, x) = q₂ (un 1 de plus), alors δ(q₀, y) = q₀ (équilibre retrouvé).
• Si y = x1 et δ(q₀, x) = q₁ (un 0 de plus), alors δ(q₀, y) = q₀.
• Les autres cas sont traités de façon similaire.

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.

Exercice 7 : Modélisation d’un dispositif à leviers par un automate

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 :

• La position des trois leviers (codée en binaire sur 3 bits l₃ l₂ l₁, où / = 0 et \ = 1).
• La sortie de la dernière bille (C ou D).

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.

Méthode : techniques récompensées et erreurs pénalisées

Ce TD récompense :

• La capacité à construire des automates déterministes en suivant précisément les contraintes du langage à reconnaître.
• L’utilisation rigoureuse des états pour mémoriser l’information nécessaire (par exemple, parité, nombre de symboles consécutifs, congruences modulo).
• La compréhension des opérations sur les automates, notamment la construction du complémentaire via l’inversion des états finaux après complétion.
• La démonstration par récurrence pour justifier la reconnaissance correcte d’un langage par un automate.
• La modélisation précise d’un système dynamique par un automate d’états.

Les erreurs pénalisées sont :

• Omettre de rendre l’automate complet avant de prendre le complémentaire.
• Confondre les états finaux et non finaux lors de la construction du complémentaire.
• Ne pas mémoriser suffisamment d’information dans les états (par exemple, ne pas suivre les deux derniers symboles pour l’avant-dernier symbole).
• Ne pas justifier les propriétés des automates par un raisonnement clair (notamment dans les exercices de preuve).
• Confondre les transitions ou ne pas respecter les contraintes sur les préfixes dans les langages complexes.