Dossier complet — Théorie des langages et automates

L3 · S6 · Fondements de l’informatique

Dossier pédagogique original Matrice MI. Contenu d’entraînement non officiel; il ne remplace pas le support ou la maquette d’un établissement.

Objectifs d’apprentissage

• Définir un langage formel, une expression régulière et les opérations usuelles sur les langages.

• Construire, simuler et vérifier un automate fini déterministe ou non déterministe.

• Transformer une description régulière en automate et justifier la correction d’une reconnaissance.

• Écrire et analyser une grammaire hors contexte en distinguant dérivation, ambiguïté et langage engendré.

• Situer un problème dans la hiérarchie de Chomsky et relier les modèles à l’analyse lexicale.

Prérequis

• Raisonnement par récurrence, ensembles, fonctions et preuves élémentaires.

• Notions de programmation : chaînes, boucles, tableaux et lecture d’un pseudo-code.

• Manipulation des graphes orientés et vocabulaire de base en algorithmique.

Cours

1. Langages reguliers

Idée centrale

Un alphabet $\Sigma$ est un ensemble fini de symboles; un mot est une suite finie de symboles, et un langage est un ensemble de mots. Les expressions régulières se construisent avec l’union, la concaténation et l’étoile de Kleene. Ainsi $a^*b$ désigne les mots formés de zéro, une ou plusieurs occurrences de $a$ suivies de $b$. La propriété fondamentale est la clôture des langages réguliers par union, concaténation et complémentation.

Méthode. Pour décrire des mots qui commencent par ab et se terminent par 0, on écrit ab(0|1)*0; il faut vérifier séparément les longueurs minimales et les recouvrements. Une erreur fréquente consiste à confondre l’étoile, qui autorise zéro occurrence, avec le plus, qui en impose au moins une. Exemple guidé : a*(ba*)* accepte ε, aaa, ba, aabaa; aab se décompose en aa puis b, donc est accepté. Point de contrôle : donner un mot refusé et expliquer le sous-terme qui échoue.

Points-clés

• Un langage est un ensemble de mots sur un alphabet fini.
• Union, concaténation et étoile de Kleene expriment les constructions régulières.
• Toujours tester ε, un mot minimal, un mot limite et un contre-exemple.

2. Automates finis

Reconnaître par états

Un automate fini déterministe est un quintuplet $A=(Q,\Sigma,\delta,q_0,F)$, où $\delta:Q\times\Sigma\to Q$ est totale, $q_0$ l’état initial et $F$ l’ensemble des états acceptants. Un mot est accepté si l’état atteint après sa lecture appartient à $F$. Un automate non déterministe peut proposer plusieurs transitions, voire des transitions $\varepsilon$; il reconnaît exactement les langages réguliers, mais sa simulation doit suivre un ensemble d’états.

Méthode. Pour compter la parité des 1, prendre $q_E$ initial et final, $q_O$ non final; sur 0, boucler, sur 1, alterner. Pour 10110, le parcours est $q_E\to q_O\to q_O\to q_E\to q_O\to q_O$ : le mot est refusé. L’erreur classique est d’oublier que l’état initial compte comme état courant avant tout symbole. La déterminisation remplace un ensemble d’états par un état du nouvel automate, puis retire les états inatteignables. Point de contrôle : simuler 1100 et justifier l’acceptation.

Points-clés

• La fonction de transition détermine un parcours unique dans un AFD.
• Les AFD et AFN ont la même puissance expressive.
• La parité se modélise naturellement par deux états et une alternance.

3. Grammaires et hiérarchie

Produire une structure

Une grammaire hors contexte $G=(V,\Sigma,P,S)$ comporte des non-terminaux, des terminaux, des productions et un axiome. Une dérivation remplace un non-terminal par le membre droit d’une règle; le langage est l’ensemble des mots terminaux dérivables depuis $S$. Pour $S\to aSb\mid\varepsilon$, on obtient exactement $\{a^nb^n\mid n\ge0\}$.

Exemple guidé. Pour produire aabb, appliquer deux fois la règle récursive : $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$. Une dérivation gauche remplace toujours le non-terminal le plus à gauche; elle facilite la construction d’un analyseur. Une grammaire est ambiguë si un mot possède deux arbres de dérivation distincts, ce qui peut modifier l’interprétation d’expressions. Erreurs fréquentes : confondre terminal et non-terminal, oublier la dérivation vide ou conclure qu’une grammaire est régulière parce qu’elle est courte. Point de contrôle : dériver aaabbb et prouver par invariant que tout mot produit comporte autant de a que de b.

Points-clés

• Une production hors contexte remplace un seul non-terminal.
• Les dérivations et arbres décrivent la structure des mots produits.
• L’ambiguïté concerne plusieurs analyses pour un même mot.

4. Équivalences, minimisation et propriétés de clôture

Réduire sans changer le langage

Deux états sont équivalents si aucun suffixe ne permet de distinguer leurs comportements d’acceptation. La relation de Myhill-Nerode formalise cette idée : les classes de l’équivalence d’indistinguabilité correspondent aux états d’un automate minimal, à isomorphisme près. En pratique, la table de distinction marque d’abord les paires dont un seul état est final, puis propage une marque lorsqu’une transition mène vers une paire déjà distinguée.

Exemple guidé. Dans un automate dont $q_1$ et $q_2$ sont tous deux non finaux et, pour chaque symbole, ont exactement les mêmes destinations modulo les mêmes classes, aucune chaîne ne les sépare : on les fusionne. Pour vérifier le complément, il faut un AFD complet; on échange alors états finaux et non finaux. Les erreurs fréquentes sont de minimiser un AFN directement ou d’oublier l’état-puits lors d’une transition manquante. Point de contrôle : expliquer pourquoi l’intersection se construit par produit des états et pourquoi le produit finit.

Vérification

Le produit de deux automates suit simultanément leurs parcours.

Points-clés

• Deux états équivalents acceptent les mêmes suffixes.
• La minimisation fusionne uniquement des états indiscernables.
• Complément et produit exigent de surveiller la complétude et les états atteignables.

5. Hiérarchie de Chomsky et analyse lexicale

Choisir le bon modèle

La hiérarchie usuelle emboîte les langages réguliers, algébriques, contextuels et récursivement énumérables; chaque inclusion est stricte. Un langage comme les identifiants ou les constantes entières est souvent régulier et convient à un automate. Les parenthèses équilibrées demandent une mémoire de pile et sont typiquement algébriques, tandis que $\{a^nb^nc^n\}$ n’est pas algébrique.

Exemple guidé. Pour un analyseur lexical, définir des jetons ENTIER, ID, PLUS, ignorer les espaces, puis choisir la règle correspondant au plus long préfixe; sur sum+12, on produit ID(sum), PLUS, ENTIER(12). L’ordre des règles départage les mots-clés et identifiants, par exemple if avant ID. Une erreur fréquente est de demander au lexer de vérifier une structure imbriquée, responsabilité du parseur. Point de contrôle : expliquer pourquoi ((x)) nécessite un compteur ou une pile, alors que x12 peut être reconnu par une expression régulière.

Limite pratique

Un modèle plus expressif ne garantit pas un analyseur plus simple.

Points-clés

• Les classes de Chomsky se distinguent par la mémoire disponible.
• Le lexer reconnaît des jetons locaux et applique le plus long préfixe.
• Les structures imbriquées relèvent généralement du parsing et d’une pile.

Exercices corrigés

Exercice 1 · Fondamental

Construire un AFD sur Σ={0,1} qui accepte exactement les mots contenant un nombre pair de 1, puis simuler le mot 101101.

Correction détaillée

Créer qE initial et final, et qO non final. Sur 0, chaque état boucle; sur 1, qE va vers qO et qO vers qE. Pour 101101 : qE→qO (1), →qO (0), →qE (1), →qO (1), →qE (0), →qO (1). Le mot contient trois 1, donc l’état final est qO : il est refusé. La construction accepte précisément les parités paires car chaque 1 inverse la parité et chaque 0 la conserve.

Exercice 2 · Fondamental

Donner une expression régulière sur {a,b} pour les mots qui commencent par ab et contiennent ensuite n’importe quelle suite de a et b, mais se terminent par b. Vérifier ab, abb et aba.

Correction détaillée

Le préfixe imposé est ab, le milieu peut être vide ou arbitraire, et le dernier symbole doit être b. Une expression est ab(a|b)*b. ab est refusé car il manque le dernier b; abb est accepté avec un milieu vide; aba est refusé car son dernier symbole est a. Attention : si l’on voulait autoriser le mot minimal ab lui-même, il faudrait traiter ce cas séparément, car le b final ne peut pas être le même symbole que celui du préfixe dans cette expression.

Exercice 3 · Intermédiaire

Un AFN a q0 initial, q2 final, transitions q0 --a→ {q0,q1}, q1 --b→ {q2}, et aucune autre transition. Déterminiser et donner les états atteignables, puis décider le mot aab.

Correction détaillée

Les états de l’AFD sont des ensembles. D={q0}; sur a, D va vers {q0,q1}; sur b, vers l’ensemble vide. Depuis {q0,q1}, sur a on revient à {q0,q1}; sur b on obtient {q2}. Depuis {q2}, toute transition va vers ∅, état-puits. L’état final est tout ensemble contenant q2, ici {q2}. Pour aab : {q0} --a→ {q0,q1} --a→ {q0,q1} --b→ {q2}; le mot est accepté. L’état ∅ rend la fonction de transition totale.

Exercice 4 · Intermédiaire

Pour G : S→aSb | ε, montrer que le mot aaabbb est engendré et expliquer pourquoi aucun mot produit ne contient un nombre différent de a et de b.

Correction détaillée

Dérivation gauche : S⇒aSb⇒aaSbb⇒aaaSbbb⇒aaabbb, en choisissant trois fois la règle récursive puis ε. Pour la propriété, utiliser une induction sur le nombre de règles récursives : à zéro étape, ε contient 0 a et 0 b; si un mot contient autant de chaque symbole, appliquer S→aSb ajoute exactement un a au début et un b à la fin, donc l’égalité est conservée. Ainsi tout mot produit est a^n b^n. Réciproquement, toute valeur n s’obtient par n applications récursives puis ε. Le langage est donc exactement {a^n b^n | n≥0}.

Exercice 5 · Avancé

Justifier une méthode de minimisation par table pour un AFD complet, puis appliquer le principe à quatre états q0,q1,q2,q3 où q0,q1 sont non finaux, q2,q3 finaux, et les transitions de q0 et q1 coïncident toujours après remplacement de q0 par q1.

Correction détaillée

Écrire toutes les paires non ordonnées. Marquer d’abord les paires de statut différent (final/non final). Pour chaque paire non marquée (p,r), chercher un symbole x tel que (δ(p,x),δ(r,x)) soit déjà marquée; marquer alors (p,r), jusqu’à stabilité. Les paires restantes sont équivalentes et peuvent être fusionnées; la stabilité garantit qu’aucun suffixe ne les distingue. Ici, les transitions de q0 et q1 aboutissent toujours dans des états qui ont le même comportement par hypothèse : la paire (q0,q1) reste non marquée et se fusionne. Les paires opposant q0 ou q1 à q2 ou q3 sont marquées immédiatement. On obtient un automate à trois classes au plus, en retirant ensuite les états inatteignables.

Quiz d’autoévaluation

Question 1

Quel élément indique qu’un mot est accepté par un AFD après sa lecture ?

• La longueur du mot ✓ L’état courant appartient à F • Le premier symbole est 0 • Le nombre d’états visités est pair

Explication : Par définition, un mot est accepté lorsque l’état atteint après lecture complète appartient à l’ensemble final F.

Question 2

Que signifie a* dans une expression régulière ?

• Exactement une occurrence de a • Au moins deux occurrences de a ✓ Zéro ou plusieurs occurrences de a • Une occurrence de a suivie de b

Explication : L’étoile de Kleene autorise toutes les répétitions finies, y compris zéro : elle contient donc le mot vide.

Question 3

Quel automate reconnaît exactement les mêmes langages qu’un AFN ?

✓ Un AFD • Un automate à pile uniquement • Un automate sans état final • Un graphe non orienté

Explication : La construction par sous-ensembles transforme tout AFN en AFD équivalent, même si le nombre d’états peut augmenter.

Question 4

Quelle condition est nécessaire pour compléter un AFD avant de prendre son complément ?

• Chaque état doit être final • Chaque paire d’états doit être fusionnée ✓ Chaque état doit avoir une transition définie pour chaque symbole • L’alphabet doit avoir un seul symbole

Explication : Le complément échange final et non-final; cela n’est correct que si tout mot possède un parcours, donc si la transition est totale.

Question 5

Dans S→aSb | ε, que produit une application de aSb ?

✓ Un a et un b autour du sous-mot dérivé • Deux a consécutifs seulement • Un mot de longueur impaire toujours • Une transition d’automate

Explication : La règle ajoute un a à gauche et un b à droite, en conservant le sous-mot dérivé entre les deux.

Question 6

Quel modèle convient naturellement aux parenthèses correctement imbriquées ?

• Un automate fini sans mémoire ✓ Un automate à pile • Un simple tableau de fréquences • Une expression régulière seule

Explication : Une pile mémorise un nombre non borné d’ouvertures et les dépile lors des fermetures; cette mémoire dépasse celle d’un automate fini.

Question 7

Que fait en priorité un analyseur lexical dans un compilateur ?

• Prouver tous les théorèmes du programme ✓ Découper le texte en jetons • Exécuter les instructions machine • Minimiser toute grammaire

Explication : Le lexer regroupe les caractères en unités comme identifiants, nombres et opérateurs avant l’analyse syntaxique.

Question 8

Quel langage est un exemple classique non régulier ?

• a* • (a|b)* ✓ {a^n b^n | n≥0} • Le langage des mots de longueur paire

Explication : Un automate fini ne peut pas mémoriser une quantité non bornée de a pour la comparer ensuite au nombre de b; le lemme de pompage le montre formellement.

Glossaire

• Alphabet — Ensemble fini de symboles autorisés pour construire les mots d’un langage.
• Mot vide — Mot noté ε, de longueur nulle, qui est neutre pour la concaténation.
• Langage régulier — Langage reconnu par un automate fini ou décrit par une expression régulière.
• AFD — Automate fini déterministe dont chaque couple état-symbole possède une destination unique.
• AFN — Automate fini non déterministe pouvant proposer plusieurs destinations pour un symbole.
• Grammaire hors contexte — Système de productions où chaque règle réécrit un seul non-terminal indépendamment du contexte.
• Dérivation — Suite de réécritures partant de l’axiome et aboutissant éventuellement à un mot terminal.
• Minimisation — Réduction d’un AFD en fusionnant les états qui ne peuvent être distingués par aucun suffixe.

TP · Mini-analyseur lexical de commandes

Une petite console accepte des commandes comme load fichier, add 12, quit. On veut vérifier lexicalement les lignes avant de les transmettre à un parseur.

Objectifs

• Définir un alphabet de caractères et des jetons non ambigus.

• Construire un AFD ou une table de transitions pour identifiants et entiers.

• Implémenter une simulation qui applique le plus long préfixe.

• Tester les rejets et documenter les limites du lexer.

Étapes

1. Écrire les expressions régulières des mots-clés, identifiants, entiers et espaces.

2. Construire les automates correspondants puis les réunir avec une priorité de jetons.

3. Coder une fonction nextToken qui renvoie type, lexème et position, ou une erreur.

4. Tester au moins load data, add 12, add -3, une chaîne vide et un caractère interdit.

5. Comparer les sorties attendues aux sorties observées et expliquer deux choix de conception.

Livrables attendus

• Un schéma ou tableau des états et transitions annoté.

• Le code source et un fichier de tests reproductibles.

• Une note courte avec jetons, règles de priorité, exemples acceptés et limites.

Critères d’évaluation

• 4 points : jetons et automates couvrent correctement les cas annoncés.

• 3 points : simulation et erreurs donnent des positions exactes.

• 2 points : tests comprennent cas limites et rejets justifiés.

• 1 point : documentation claire, distinction lexer/parseur respectée.

Piste de résolution

Définir ID par [A-Za-z][A-Za-z0-9]*, ENTIER par [0-9]+, ESPACE par [ \t]+, puis réserver load, add et quit après reconnaissance d’un ID. À chaque position, essayer les règles et conserver le lexème valide le plus long; départager les longueurs égales par une priorité documentée. Ignorer ESPACE, avancer l’indice après chaque jeton et produire une erreur sur absence de règle. Les signes négatifs peuvent être un jeton séparé ou une extension d’ENTIER, mais le choix doit être uniforme dans les tests.

Sujets originaux d’entraînement (non officiels)

Sujet original de préparation — session normale

Sujet original d’entraînement non officiel; il ne provient pas d’une session d’examen antérieure. Ce sujet est une création originale non officielle. Il ne constitue ni une véritable épreuve ni une annale d’années passées.

Exercice 1

Construire un AFD reconnaissant les mots binaires qui se terminent par 01. Donner les transitions et simuler 1101.

Correction : Utiliser trois états représentant le plus long suffixe pertinent : q0 (aucun suffixe utile), q1 (dernier symbole 0), q2 (suffixe 01), seul q2 final. Depuis q0, 0→q1 et 1→q0; depuis q1, 0→q1 et 1→q2; depuis q2, 0→q1 et 1→q0. Pour 1101 : q0→q0→q0→q1→q2, donc acceptation.

Exercice 2

Donner une grammaire hors contexte pour {a^n b^n | n≥0}, puis fournir un arbre ou une dérivation de aabb.

Correction : Prendre S→aSb | ε. Dériver S⇒aSb⇒aaSbb⇒aabb. La règle récursive ajoute un a et un b; ε fournit le cas n=0. Une induction sur le nombre d’applications montre que tout mot produit est a^n b^n, et la construction inverse montre que chaque n est obtenu.

Exercice 3

Expliquer pourquoi le complément d’un langage régulier est régulier et préciser la condition sur l’automate utilisé.

Correction : Tout langage régulier possède un AFD. Le compléter consiste à ajouter un état-puits et les transitions manquantes afin que δ soit totale. En échangeant F et Q\F, chaque mot accepté devient refusé et réciproquement, car tout mot possède désormais un parcours unique. L’automate obtenu reconnaît le complément; sans complétude, un mot bloqué serait confondu à tort avec un mot dont le parcours termine dans un état non final.

Sujet original de préparation — seconde session

Sujet original d’entraînement non officiel; il ne provient pas d’une session d’examen antérieure. Ce sujet est une création originale non officielle. Il ne constitue ni une véritable épreuve ni une annale d’années passées.

Exercice 1

Déterminiser l’AFN ayant q0 initial, q1 final, q0 --0→{q0,q1}, q0 --1→{q0}, q1 --1→{q1}. Décider 001.

Correction : Les ensembles atteignables sont {q0} initial et {q0,q1} final. Depuis {q0}, 0→{q0,q1}, 1→{q0}; depuis {q0,q1}, 0→{q0,q1}, 1→{q0,q1}. Le mot 001 suit {q0}→{q0,q1}→{q0,q1}→{q0,q1}; il est accepté. L’ensemble vide n’est pas atteint ici, mais peut être ajouté pour totaliser l’AFD.

Exercice 2

Montrer que le langage des parenthèses bien équilibrées n’est pas régulier à l’aide de l’intuition du lemme de pompage.

Correction : Supposer le langage régulier de longueur de pompage p et choisir w=(^p )^p. Toute factorisation w=xyz avec |xy|≤p et |y|>0 place y uniquement dans les premières ouvertures. Pomper y zéro fois donne moins d’ouvertures que de fermetures, donc un mot qui n’est plus équilibré, contradiction. La structure exige de mémoriser une profondeur non bornée; un automate fini ne le peut pas.

Exercice 3

Concevoir une stratégie de analyse lexicale pour if x12==10 en distinguant le mot-clé if, l’identifiant, l’égalité et l’entier.

Correction : Définir les règles IF=if, ID=[A-Za-z][A-Za-z0-9]*, EQ===, INT=[0-9]+, ESPACE ignoré. À chaque position, choisir le plus long préfixe; en cas d’égalité de longueur, donner priorité au mot-clé et à l’opérateur. La sortie est IF(if), ID(x12), EQ(==), INT(10). Il faut tester iffy, qui doit être ID(iffy) et non IF suivi d’un identifiant : la règle mot-clé ne s’applique que si le lexème est délimité comme un jeton complet.

Parcours de révision sur quatre semaines

Semaine 1 · Mots, langages réguliers et expressions régulières

Refaire les définitions, simplifier dix expressions, puis tester ε et des contre-exemples dans un tableau. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 2 · AFD, AFN, déterminisation et minimisation

Dessiner deux automates, simuler quinze mots, convertir un AFN et appliquer une table de distinctions. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 3 · Grammaires hors contexte et hiérarchie

Produire des dérivations gauche, repérer une ambiguïté et rédiger une preuve de non-régularité guidée. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 4 · Analyse lexicale et synthèse

Réaliser le mini-analyseur lexical, corriger les exercices, faire un sujet original en temps limité puis vérifier chaque justification. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.