Théorie des Langages et Compilation

Ce matériel couvre les bases de la théorie des langages formels et des automates, destiné aux étudiants en informatique souhaitant comprendre la reconnaissance, la génération et la représentation des langages, ainsi que leur application à la compilation.

Mots et langages

Vocabulaire et mot

Un alphabet (ou vocabulaire) est un ensemble fini et non vide de symboles, noté généralement X.

La fermeture de Kleene d’un alphabet X, notée X*, est l’ensemble de toutes les séquences finies de symboles de X, incluant la chaîne vide e.

La chaîne vide e est un mot ne contenant aucun symbole, élément de X*.

La longueur d’un mot w, notée |w|, est le nombre de symboles qu’il contient.

Un mot w est une application d’un segment initial [1..n] vers l’alphabet X, où chaque position i du mot correspond à un symbole w_i dans X.

Exemple

Soit le vocabulaire X = {a, b} et le mot w = "abba". Les symboles aux positions sont :

• w_1 = a
• w_2 = b
• w_3 = b
• w_4 = a

La longueur de ce mot est |abba| = 4.

Le nombre d’occurrences d’un symbole x dans un mot w, noté |w|_x, est le nombre de fois où x apparaît dans w. Par exemple, |abba|_b = 2.

Langage

Un langage L sur un alphabet X est un sous-ensemble de X*.

Exemples :

• Si X = {0,1,...,9}, L peut être l’ensemble des représentations décimales des nombres entiers naturels.
• Si X = {x1, x2, +, *, (, )}, L peut être l’ensemble des expressions arithmétiques parenthésées manipulant ces symboles.
• Si X est le vocabulaire du langage C, L peut être l’ensemble des programmes C syntaxiquement corrects.
• Si X est le vocabulaire de la logique des propositions, L peut être l’ensemble des formules bien formées.

Opérations sur les langages

Pour deux mots u et v, leur concaténation u.v est le mot obtenu en enchaînant u puis v.

Le mot vide e est l’élément neutre de la concaténation : u.e = e.u = u.

Pour deux langages A et B, on définit :

• Intersection : A ˙ B = {w | w ∈ A et w ∈ B}
• Union : A + B = {w | w ∈ A ou w ∈ B}
• Complément : A - B = {w | w ∈ A et w ∉ B}
• Concaténation : A.B = {w | w = u.v avec u ∈ A et v ∈ B}

Propriétés :

• A.(B + C) = A.B + A.C
• (A + B).C = A.C + B.C
• Si A ⊆ B alors A.C ⊆ B.C et C.A ⊆ C.B

Notation :

• a^k = a répété k fois (par exemple a^2 = aa)
• a^0 = e (mot vide)
• a* = {a^i | i ≥ 0} = {e, a, aa, aaa, ...}
• a+ = {a^i | i > 0} = {a, aa, aaa, ...}

L’opération étoile * sur un langage A est définie par :

A* = ⋃_{i≥0} A^i avec A^0 = {e} et A^i = A.A^{i-1} pour i ≥ 1.

L’opération + est définie par :

A+ = ⋃_{i≥1} A^i.

Exemple

Soit A = {a}, alors :

• A* = {e, a, aa, aaa, ...} = a*

Si A = {w | w ∈ X*, |w| = 2k+1, k ≥ 0}, alors A* = X*.

Propriétés supplémentaires

• A.∅ = ∅
• A.{e} = {e}.A = A
• En général, A.(B + C) ≠ A.B + A.C (contre-exemple donné)
• A+ ≠ A* - {e} si A contient e

Définition de langages par propriété mesurable ou récursive

• Langage des mots sur {a,b} de longueur paire : L = {w ∈ {a,b}* | |w| = 2k, k ≥ 0}
• Langage des mots sur {a,b} avec un nombre impair de b : L = {w ∈ {a,b}* | |w|_b = 2k+1, k ≥ 0}
• Langage des mots sur {a,b} où tous les a précèdent les b et sont en nombre égal : L = {a^n b^n | n ≥ 0}

Définition récursive du langage L = {a^n b^n | n ≥ 0} :

• e ∈ L
• Si w ∈ L alors awb ∈ L

Définition récursive des palindromes sur {a,b} :

• Pour longueur paire :
• e ∈ L
• aa, bb ∈ L
• Si w ∈ L alors a w a ∈ L et b w b ∈ L
• Pour longueur impaire :
• a, b ∈ L
• Si w ∈ L alors a w a ∈ L et b w b ∈ L
• Pour tous palindromes :
• e, a, b ∈ L
• aa, bb ∈ L
• Si w ∈ L alors a w a ∈ L et b w b ∈ L

Le lemme d’Arden

Pour deux langages A et B sur un alphabet X*, les équations :

• L = A.L + B
• L = L.A + B

admettent respectivement comme solution minimale :

• L = A* B
• L = B A*

Cette solution est unique si e ∉ A.

Les automates finis et les langages réguliers

Automates finis déterministes

Un automate fini est un quintuple (Q, X, d, q0, F) où :

• Q est un ensemble fini d’états
• X est un alphabet
• d : Q × X → Q est la fonction de transition
• q0 ∈ Q est l’état initial
• F ⊆ Q est l’ensemble des états finaux

Exemple simple

Automate A avec :

• Q = {OFF, ON}
• X = {presser}
• q0 = OFF
• F = {ON}
• d(OFF, presser) = ON
• d(ON, presser) = OFF

Ce modèle reconnaît les séquences de "presser" qui, partant de OFF, aboutissent à ON.

Par exemple, la séquence "presser presser presser" est acceptée car elle mène à l’état ON après trois transitions.

Langage accepté par cet automate

Le langage L(A) est l’ensemble des séquences de "presser" de longueur impaire :

L(A) = { w ∈ {presser}* | |w| = 2k + 1, k ≥ 0 }

Exemple d’automate acceptant les mots de longueur paire sur {a}

Automate avec états {I, P}, I initial et final, transitions :

• d(I, a) = P
• d(P, a) = I

Ce langage est (aa)*, incluant e (mot vide) car I est final.

Exercices de construction d’automates

• Automate acceptant {a}* avec longueur paire (k > 0) : le plus petit mot accepté est "aa".
• Automate acceptant {a,b}* où le nombre de a est congru à 2 modulo 3 : états q0, q1, q2 comptant les a lus modulo 3, avec transitions sur a et b.
• Automate acceptant {a}* où la longueur est 3k+1 : mots commençant par a suivi de multiples de 3 a.
• Automate acceptant {a,b,c}* où le nombre de a est 3k+1, avec b et c ignorés dans le comptage.
• Automate acceptant les mots contenant "aba" comme facteur.
• Automate acceptant les représentations décimales des entiers avec le chiffre 1 dans les dizaines.
• Automate acceptant les entiers décimaux différents de zéro.

Définitions importantes

• Automate fini complet : pour chaque état q et symbole s, il existe au moins une transition d(q, s).
• Automate fini non ambigu : pour chaque état q et symbole s, il existe au plus une transition d(q, s).
• Automate fini déterministe : complet et non ambigu, c’est-à-dire exactement une transition par symbole et état.

Exemples d’automates non complets, ambigus et déterministes

Un automate non complet manque des transitions pour certains symboles.

Un automate ambigu a plusieurs transitions possibles pour un même état et symbole.

Un automate déterministe a une transition unique par état et symbole.

Langage accepté par un automate fini

Une configuration est un couple (q, w) où q est l’état courant et w la partie restante du mot à lire.

Une configuration (p, y) est successeur de (q, x) si x = a y et d(q, a) = p.

Le langage reconnu par un automate A = (Q, X, d, q0, F) est :

L(A) = { w | (q0, w) ⊢* (qf, e), qf ∈ F }

Autrement dit, w est accepté si la lecture de w mène de l’état initial à un état final.

Exemple

Pour l’automate A donné, on a :

• aa ∈ L(A) car (q0, aa) ⊢* (q2, e)
• bba ∉ L(A) car la lecture ne mène pas à un état final

Application du lemme d’Arden aux automates

Soit un automate A avec états q0, q1, q2 et transitions sur a, on peut écrire des équations sur les langages Li reconnus depuis qi :

• L0 = {a} L0 + {a} L1 + {e}
• L1 = {a} L2
• L2 = {a} L0 + {e}

En résolvant ces équations avec le lemme d’Arden, on obtient :

L0 = (aaa)* aa

Exemple d’automate reconnaissant a*b*

Automate avec deux états q0 et q1 :

• d(q0, a) = q0
• d(q0, b) = q1
• d(q1, b) = q1

Les langages associés sont :

• L1 = b*
• L0 = a* b*

Ce qui confirme que l’automate reconnaît a*b*.

Automate reconnaissant (a+b)*

Automate à un seul état q0, initial et final, avec transitions sur a et b vers q0.

L0 = {a} L0 + {b} L0 + {e} = (a+b)*

Rendre déterministe un automate fini non déterministe

Automate non complet

Pour rendre un automate non complet déterministe, on ajoute un état "puit" et on complète les transitions manquantes vers cet état.

Automate ambigu

Pour rendre un automate ambigu déterministe, on construit un automate dont les états sont des ensembles d’états de l’automate initial (construction par déterminisation).

Étapes :

1. Définir les nouveaux états comme groupes d’états visités simultanément.
2. Renommer ces groupes et définir les états finaux (un état est final s’il contient un état final initial).
3. Construire la fonction de transition sur ces nouveaux états.

Exemple de déterminisation

Automate initial avec états q0, q1 :

• États du déterministe : {q0}, {q0,q1}, {q1}
• Transitions définies en fonction des transitions possibles dans l’automate initial.

Langages réguliers

Définition

Un langage L est régulier s’il existe un automate fini A tel que L = L(A).

Lemme de pompage

Si L est régulier et reconnu par un automate à n états, alors tout mot z ∈ L de longueur ≥ n peut être factorisé en z = uvw avec |uv| ≤ n, v ≠ e, et pour tout i ≥ 0, u v^i w ∈ L.

Exemples d’applications

• Le langage L = {0^n 1^n | n ≥ 0} n’est pas régulier (contradiction avec le lemme de pompage).
• Le langage des écritures binaires de nombres premiers n’est pas régulier.

Propriétés des langages réguliers

• Si L1 et L2 sont réguliers, alors L1 + L2 (union), L1.L2 (concaténation), et L1 ˙ L2 (intersection) sont réguliers.
• Si L est régulier, alors L*, L+, le complément X - L et l’image miroir sont réguliers.

Construction d’automates pour les opérations sur langages réguliers

Pour l’union :

• Soient A1 = (Q1, X1, d1, q01, F1) et A2 = (Q2, X2, d2, q02, F2) acceptant L1 et L2.
• Construire A = (Q, X, d, q0, F) avec :
• Q = Q1 ∪ Q2 ∪ {q0}
• X = X1 ∪ X2
• d étend d1 et d2 et ajoute transitions de q0 vers q01 et q02
• F = F1 ∪ F2 ∪ {q0 si q01 ∈ F1 ou q02 ∈ F2}

Pour la concaténation :

• Q = Q1 ∪ Q2
• X = X1 ∪ X2
• q0 = q01
• Les transitions de d sont celles de d1 et d2, avec transitions de chaque état final de A1 vers q02
• F = F2

Exemples d’exercices

• Construire un automate acceptant L(A1) + L(A2) à partir de deux automates A1 et A2 donnés.
• Construire un automate acceptant L(A1).L(A2) à partir de deux automates A1 et A2 donnés.

Glossaire des termes clés

• Alphabet (X) : Ensemble fini non vide de symboles.
• Mot : Séquence finie de symboles de l’alphabet.
• Chaîne vide (e) : Mot ne contenant aucun symbole.
• Longueur d’un mot (|w|) : Nombre de symboles dans le mot.
• Langage : Sous-ensemble de X*, ensemble de mots sur un alphabet X.
• Concaténation : Opération qui enchaîne deux mots ou langages.
• Fermeture de Kleene (*) : Ensemble des concaténations finies (y compris la chaîne vide) d’un langage.
• Automate fini : Machine à états finis définie par (Q, X, d, q0, F).
• Automate fini déterministe : Automate fini complet et non ambigu.
• Configuration : Couple (état courant, mot restant à lire).
• Langage reconnu par un automate : Ensemble des mots menant l’automate d’un état initial à un état final.
• Lemme d’Arden : Résolution d’équations sur langages avec solutions en termes de fermetures de Kleene.
• Langage régulier : Langage reconnu par un automate fini.
• Lemme de pompage : Propriété caractéristique des langages réguliers utilisée pour démontrer que certains langages ne sont pas réguliers.
• Automate fini non déterministe : Automate pouvant avoir plusieurs transitions possibles pour un même état et symbole.
• Déterminisation : Construction d’un automate fini déterministe équivalent à un automate non déterministe.

Points clés à retenir

• Un alphabet est un ensemble fini de symboles, et un langage est un ensemble de mots construits sur cet alphabet.
• Les opérations sur les langages (union, concaténation, étoile) permettent de construire des langages complexes à partir de langages simples.
• Un automate fini déterministe est un modèle mathématique simple pour reconnaître des langages réguliers.
• Le lemme d’Arden permet de résoudre des équations sur langages et de caractériser certains langages acceptés par des automates.
• Le lemme de pompage est un outil essentiel pour prouver qu’un langage n’est pas régulier.
• Les langages réguliers sont fermés sous union, concaténation, étoile, complément et intersection.
• Tout automate fini non déterministe peut être transformé en un automate fini déterministe équivalent par la déterminisation.