Langages Formels

Plan
1 Introduction
Langages reconnaissables
Langages formels
Automates d’arbres
Paul Gastin
Grammaires
Paul.Gastin@lsv.ens-cachan.fr
http://www.lsv.ens-cachan.fr/~gastin/Langages/ Langages algébriques
L3 Informatique Cachan
2014-2015
Automates à pile
Analyse syntaxique
Fonctions séquentielles
1/197 2/197
Motivations Références
[7] Olivier Carton.
Langages formels, calculabilité et complexité.
Vuibert, 2008.
Définition : [9] John E. Hopcroft et Je↵rey D. Ullman.
1. Description et analyse (lexicale et syntaxique) des langages (programmation, Introduction to automata theory, languages and computation.
naturels, . . . ) Addison-Wesley, 1979.
2. Modèles de calcul [10] Dexter C. Kozen.
3. Abstractions mathématiques simples de phénomènes complexes dans le but de Automata and Computability.
I Prouver des propriétés. Springer, 1997.
I Concevoir des algorithmes permettant de tester des propriétés ou de résoudre [13] Jacques Sakarovitch.
des problèmes. Éléments de théorie des automates.
4. Types de données Vuibert informatique, 2003.
[8] Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis
Lugiez, Sophie Tison, Marc Tommasi.
Tree Automata Techniques and Applications.
http://www.grappa.univ-lille3.fr/tata/
3/197 4/197
Références Références
[5] Jean-Michel Autebert, Jean Berstel et Luc Boasson.
[1] Alfred V. Aho, Ravi Sethi et Je↵rey D. Ullman. Context-Free Languages and Pushdown Automata.
Compilers: principles, techniques and tools. Handbook of Formal Languages, Vol. 1, Springer, 1997.
Addison-Wesley, 1986. [6] Jean Berstel.
[2] Alfred V. Aho et Je↵rey D. Ullman. Transduction and context free languages.
The theory of parsing, translation, and compiling. Volume I: Parsing. Teubner, 1979.
Prentice-Hall, 1972. [11] Jean-Éric Pin.
[3] Luc Albert, Paul Gastin, Bruno Petazzoni, Antoine Petit, Nicolas Puech et Automates finis et applications.
Pascal Weil. Polycopié du cours à l’École Polytechnique, 2004.
Cours et exercices d’informatique. [12] Grzegorz Rozenberg et Arto Salomaa, éditeurs.
Vuibert, 1998. Handbook of Formal Languages,
[4] Jean-Michel Autebert. Vol. 1, Word, Language, Grammar,
Théorie des langages et des automates. Springer, 1997.
Masson, 1994. [14] Jacques Stern.
Fondements mathématiques de l’informatique.
Mc Graw Hill, 1990.
5/197 6/197
Plan Bibliographie
Introduction
[4] Jean-Michel Autebert.
2 Langages reconnaissables
Théorie des langages et des automates.
Mots Masson, 1994.
Langages [7] Olivier Carton.
Automates déterministes Langages formels, calculabilité et complexité.
Automates non déterministes Vuibert, 2008.
Automates avec "-transitions [9] John E. Hopcroft et Je↵rey D. Ullman.
Propriétés de fermeture Introduction to automata theory, languages and computation.
Langages rationnels Addison-Wesley, 1979.
Critères de reconnaissabilité [10] Dexter C. Kozen.
Minimisation Automata and Computability.
Springer, 1997.
Logique MSO
Morphismes et congruences [13] Jacques Sakarovitch.
Éléments de théorie des automates.
Vuibert informatique, 2003.
Automates d’arbres
Grammaires 7/197 8/197
Langages algébriques
Mots Mots
A ou ⌃ : alphabet (ensemble fini). Ordres partiels :

u 2 ⌃⇤ : mot = suite finie de lettres. I u préfixe de v si 9u0 , v = uu0
I u suffixe de v si 9u0 , v = u0 u
· : concaténation associative.
I u facteur de v si 9u0 , u00 , v = u0 uu00
" ou 1 : mot vide, neutre pour la concaténation.
I u sous-mot de v si v = v0 u1 v1 u2 · · · un vn avec ui , vi 2 ⌃⇤ et u = u1 u2 · · · un
(⌃⇤ , ·) : monoı̈de libre engendré par ⌃.
|u| : longueur du mot u. Théorème : Higman

| · | : ⌃⇤ ! N est le morphisme défini par |a| = 1 pour a 2 ⌃.
|u|a : nombre de a dans le mot u. L’ordre sous-mot est un bon ordre, i.e.
(de toute suite infinie on peut extraire une sous-suite infinie croissante)
(ou tout ensemble de mots a un nombre fini d’éléments minimaux)
ũ : miroir du mot u.
9/197 10/197
Langages Langages
Langage = sous-ensemble de ⌃⇤ .
Exemples.
Itération : L0 = {"},
S L
n+1
= Ln S · L = L · Ln ,
L⇤ = n 0 Ln , L+ = n>0 Ln .
Opérations sur les langages : soient K, L ✓ ⌃⇤ Exemples : ⌃n , ⌃⇤ , (⌃2 )⇤ .
Ensemblistes : union, intersection, complément, di↵érence, . . .

Quotients : K 1 · L = {v 2 ⌃⇤ | 9u 2 K, u · v 2 L}
Concaténation : K · L = {u · v | u 2 K et v 2 L} L · K 1 = {u 2 ⌃⇤ | 9v 2 K, u · v 2 L}
La concaténation est associative et distributive par rapport à l’union.
|K · L|  |K| · |L|
notion de multiplicité, d’ambiguı̈té
11/197 12/197
Automates déterministes Automates déterministes
Définition : Automate déterministe
A = (Q, , i, F )
Q ensemble fini d’états, i 2 Q état initial, F ✓ Q états finaux, Langage accepté (reconnu) par A : L(A) = {u 2 ⌃⇤ | (i, u) 2 F }.
: Q ⇥ ⌃ ! Q fonction de transition (totale ou partielle). Exemples.
Exemples.
u
Calcul de A sur un mot u = a1 · · · an : q0 ! qn Définition : Reconnaissables
a
1 an Un langage L ✓ ⌃⇤ est reconnaissable, s’il existe un automate fini A tel que L =
q0 ! q1 · · · qn 1 ! qn L(A).
avec qi = (qi 1 , ai ) pour tout 0 < i  n.

On note Rec(⌃⇤ ) la famille des langages reconnaissables sur ⌃⇤ .
Généralisation de à Q ⇥ ⌃⇤ :
(q, ") = q,
(q, u · a) = ( (q, u), a) si u 2 ⌃⇤ et a 2 ⌃.
13/197 14/197
Automates non déterministes Automates non déterministes

Théorème : Déterminisation
Exemple : automate non déterministe pour ⌃⇤ · {aba}
Soit A un automate non déterministe. On peut construire un automate déterministe
B qui reconnaı̂t le même langage (L(A) = L(B)).
Définition : Automate non déterministe
A = (Q, T, I, F ) Preuve
Q ensemble fini d’états, I ✓ Q états initiaux, F ✓ Q états finaux, Automate des parties
T ✓ Q ⇥ ⌃ ⇥ Q ensemble des transitions.
On utilise aussi : Q ⇥ ⌃ ! 2Q . Exemple : automate déterministe pour ⌃⇤ · {aba}
On appelle déterminisé de A l’automate des parties émondé.
1 a an
Calcul de A sur un mot u = a1 · · · an : q0 ! q1 · · · qn 1 ! qn avec Exercices :
(qi 1 , ai , qi ) 2 T pour tout 0 < i  n.
1. Donner un automate non déterministe avec n états pour L = ⌃⇤ a⌃n 2
.
Langage accepté (reconnu) par A :
2. Montrer que tout automate déterministe reconnaissant ce langage L a au
u
L(A) = {u 2 ⌃⇤ | 9 i ! f calcul de A avec i 2 I et f 2 F }. moins 2n 1 états.
3. Donner un automate non déterministe à n états tel que tout automate
déterministe reconnaissant le même langage a au moins 2n 1 états.
15/197 16/197
Automates non déterministes Automates avec "-transitions
Un automate (D ou ND) est complet si 8p 2 Q, 8a 2 ⌃, (p, a) 6= ;. Exemple.
On peut toujours compléter un automate.
Définition : Automate avec "-transitions
Un automate (D ou ND) est émondé si tout état q 2 Q est
u A = (Q, T, I, F )
I accessible d’un état initial : 9i 2 I, 9u 2 ⌃⇤ tels que i ! q, Q ensemble fini d’états, I ✓ Q états initiaux, F ✓ Q états finaux,
u
I co-accessible d’un état final : 9f 2 F , 9u 2 ⌃⇤ tels que q ! f T ✓ Q ⇥ (⌃ [ {"}) ⇥ Q ensemble des transitions.
On peut calculer l’ensemble Acc(I) des états accessibles à partir de I et l’ensemble
coAcc(F ) des états co-accessibles des états finaux. 1 a an
Un calcul de A est une suite q0 ! q1 · · · qn 1 ! qn avec (qi 1 , ai , qi ) 2 T pour
tout 0 < i  n.
Corollaire :
Soit A un automate. Ce calcul reconnaı̂t le mot u = a1 · · · an (les " disparaissent).
1. On peut construire B émondé qui reconnaı̂t le même langage.
Remarque : Soit A un automate. On peut construire un automate sans
2. On peut décider si L(A) = ;.
"-transition B qui reconnaı̂t le même langage.
17/197 18/197
Décision Propriétés de fermeture

Presque tout est décidable sur les langages reconnaissables donnés par des
automates. Opérations ensemblistes
Définition : Proposition :
Problème du vide : étant donné un automate fini A, décider si L(A) = ;. La famille Rec(⌃⇤ ) est fermée par les opérations ensemblistes (union, complément,
. . . ).
Problème du mot : étant donnés un mot w 2 ⌃⇤ et un automate A, décider si
w 2 L(A). Preuve
Union : construction non déterministe.
Théorème : vide et mot Intersection : produit d’automates (préserve le déterminisme).
Le problème du vide et le problème du mot sont décidables en NLOGSPACE pour Complément : utilise la déterminisation.
les langages reconnaissables donnés par automates (déterministe ou non, avec ou
sans "-transitions). Corollaire :
On peut décider de l’égalité ou de l’inclusion de langages reconnaissables.
Plus précisément, soient L1 , L2 2 Rec(⌃⇤ ) donnés par deux automates A1 et A2 .
Preuve
On peut décider si L1 ✓ L2 .
C’est de l’accessibilité.
19/197 20/197
Propriétés de fermeture Propriétés de fermeture
Opérations liées à la concaténation
Si L ✓ ⌃⇤ , on note
Proposition : I Pref(L) = {u 2 ⌃⇤ | 9v 2 ⌃⇤ , uv 2 L},
Rec(⌃⇤ ) est fermée par concaténation et itération. I Su↵(L) = {v 2 ⌃⇤ | 9u 2 ⌃⇤ , uv 2 L},
I Fact(L) = {v 2 ⌃⇤ | 9u, w 2 ⌃⇤ , uvw 2 L}.
Concaténation :
Méthode 1 : union disjointe des automates et ajout de transitions. Proposition :
Méthode 2 : fusion d’états.
On suppose que les automates ont un seul état initial sans transition entrante et Rec(⌃⇤ ) est fermée par préfixe, suffixe, facteur.
un seul état final sans transition sortante.
Itération : Preuve
Méthode 1 : ajout de transitions. Ajouter un état pour reconnaı̂tre le mot vide. Modification des états initiaux et/ou finaux.
Méthode 2 : ajout d’"-transitions.
21/197 22/197

Morphismes
Proposition : Soient A et B deux alphabets et f : A⇤ ! B ⇤ un morphisme.
La famille Rec(⌃⇤ ) est fermée par quotients gauches et droits : Pour L ✓ A⇤ , on note f (L) = {f (u) 2 B ⇤ | u 2 L}.
Soit L 2 Rec(⌃⇤ ) et K ✓ ⌃⇤ arbitraire. Pour L ✓ B ⇤ , on note f 1 (L) = {u 2 A⇤ | f (u) 2 L}.
Les langages K 1 · L et L · K 1 sont reconnaissables.
Proposition :
Preuve
La famille des langages reconnaissables est fermée par morphisme et morphisme
Modification des états initiaux et/ou finaux. inverse.
1. Si L 2 Rec(A⇤ ) et f : A⇤ ! B ⇤ est un morphisme alors f (L) 2 Rec(B ⇤ ).
Exercice : 2. Si L 2 Rec(B ⇤ ) et f : A⇤ ! B ⇤ est un morphisme alors f 1
(L) 2 Rec(A⇤ ).
Montrer que si de plus K est reconnaissable, alors on peut e↵ectivement calculer
Preuve
les nouveaux états initiaux/finaux.
Modification des transitions de l’automate.
23/197 24/197
Proposition :
Définition : Substitutions
La famille des langages reconnaissables est fermée par substitution rationnelle et
Une substitution est définie par une application : A ! P(B ⇤ ). substitution rationnelle inverse.
Elle s’étend en un morphisme : A⇤ ! P(B ⇤ ) défini par
(") = {"} et 1. Si L 2 Rec(A⇤ ) et : A ! Rec(B ⇤ ) est une substitution rationnelle alors
(a1 · · · an ) = (a1 ) · · · (an ). (L) 2 Rec(B ⇤ ).
2. Si L 2 Rec(B ⇤ ) et : A ! Rec(B ⇤ ) est une substitution rationnelle alors
⇤
S 1
(L) 2 Rec(A⇤ ).
Pour L ✓ A , on note (L) = u2L (u).
Pour L ✓ B ⇤ , on note 1
(L) = {u 2 A⇤ | (u) \ L 6= ;}.
Une substitution est rationnelle (ou reconnaissable) si elle est définie par une appli- Preuve
cation : A ! Rec(B ⇤ ).
1. On remplace des transitions par des automates.
2. Plus difficile.
25/197 26/197
Langages rationnels Langages rationnels
Syntaxe pour représenter des langages.

Définition : Sémantique
Soit ⌃ un alphabet et ⌃ une copie de ⌃. On définit L : E ! P(⌃⇤ ) par
Une expression rationnelle (ER) est un mot sur l’alphabet ⌃ [ {(, ), +, ·, ⇤, ;} B : L(;) = ; et L(a) = {a} pour a 2 ⌃,
I : L((E + F )) = L(E) [ L(F ), L((E · F )) = L(E) · L(F ) et
L((E ⇤ )) = L(E)⇤ .
Définition : Syntaxe Un langage L ✓ ⌃⇤ est rationnel s’il existe une ER E telle que L = L(E).
L’ensemble des ER est défini par On note Rat(⌃⇤ ) l’ensemble des langages rationnels sur l’alphabet ⌃.
B : ; et a pour a 2 ⌃ sont des ER,
I : Si E et F sont des ER alors (E + F ), (E · F ) et (E ⇤ ) aussi. Remarque : Rat(⌃⇤ ) est la plus petite famille de langages de ⌃⇤ contenant ; et
On note E l’ensemble des expressions rationnelles. {a} pour a 2 ⌃ et fermée par union, concaténation, itération.
27/197 28/197
Langages rationnels Langages rationnels
Définition :
Théorème : Kleene, 1936
Deux ER E et F sont équivalentes (noté E ⌘ F ) si L(E) = L(F ).
Rec(⌃⇤ ) = Rat(⌃⇤ )
Exemples : commutativité, associativité, distributivité, . . .
Preuve
Peut-on trouver un système de règles de réécriture caractérisant l’équivalence des ◆ : les langages ; et {a} pour a 2 ⌃ sont reconnaissables et la famille
ER ? Rec(⌃⇤ ) est fermée par union, concaténation, itération.
Oui, mais il n’existe pas de système fini.
✓ : Algorithme de McNaughton-Yamada.
Comment décider de l’équivalence de deux ER ?
On va utiliser le théorème de Kleene. Corollaire :
L’équivalence des expressions rationnelles est décidable.
Abus de notation :
• On ne souligne pas les lettres de ⌃ : ((a + b)⇤ ). Preuve
• On enlève les parenthèses inutiles : (aa + bb)⇤ + (aab)⇤ . Il suffit de l’inclusion Rat(⌃⇤ ) ✓ Rec(⌃⇤ ).
• On confond langage rationnel et expression rationnelle.
29/197 30/197
Critères de reconnaissabilité Critères de reconnaissabilité
Y a-t-il des langages non reconnaissables ? Lemme : itération

Oui, par un argument de cardinalité.
Soit L 2 Rec(⌃⇤ ). Il existe N 0 tel que pour tout x 2 L,
Comment montrer qu’un langage n’est pas reconnaissable ? 1. si |x| N alors 9u1 , u2 , u3 2 ⌃⇤ tels que x = u1 u2 u3 , u2 6= " et u1 u⇤2 u3 ✓ L.
2. si x = w1 w2 w3 avec |w2 | N alors 9u1 , u2 , u3 2 ⌃⇤ tels que w2 = u1 u2 u3 ,
u2 6= " et w1 u1 u⇤2 u3 w3 ✓ L.
Exemples.
3. si x = uv1 v2 . . . vN w avec |vi | 1 alors il existe 0  j < k  N tels que
1. L1 = {an bn | n 0}, uv1 . . . vj (vj+1 . . . vk )⇤ vk+1 . . . vN w ✓ L.
2. L2 = {u 2 ⌃⇤ | |u|a = |u|b },
3. L3 = L2 \ (⌃⇤ (a3 + b3 )⌃⇤ ) Preuve
Sur l’automate qui reconnaı̂t L.
Preuves : à la main (par l’absurde). Application à L1 , L2 , L3 et aux palindromes L4 = {u 2 ⌃⇤ | u = ũ}.
31/197 32/197
Critères de reconnaissabilité Critères de reconnaissabilité
Exercice : Puissance des lemmes d’itérations Théorème : Ehrenfeucht, Parikh, Rozenberg ([13, p. 128])
1. Montrer que les langages suivants satisfont (1) mais pas (2) : Soit L ✓ ⌃⇤ . Les conditions suivantes sont équivalentes :
1. L est reconnaissable
K1 = {w 2 {a, b}⇤ | |w|a = |w|b } 2. Il existe N > 0 tel que pour tout mot x = uv1 . . . vN w 2 ⌃⇤ avec |vi | 1, il
existe 0  j < k  N tels que pour tout n 0,
K10 p n
= {b a | p > 0 et n est premier} [ {a} ⇤
2. Montrer que le langage suivant satisfait (2) mais pas (3) : x2L ssi uv1 . . . vj (vj+1 . . . vk )n vk+1 . . . vN w 2 L
K2 = {(ab)n (cd)n | n 0} [ ⌃⇤ {aa, bb, cc, dd, ac}⌃⇤ 3. Il existe N > 0 tel que pour tout mot x = uv1 . . . vN w 2 ⌃⇤ avec |vi | 1, il
existe 0  j < k  N tels que
3. Montrer que le langage suivant satisfait (3) mais n’est pas reconnaissable :
x2L ssi uv1 . . . vj vk+1 . . . vN w 2 L
K3 = {udv | u, v 2 {a, b, c}⇤ et soit u 6= v soit u ou v contient un carré}
Remarque : la preuve utilise le théorème de Ramsey.
33/197 34/197
Critères de reconnaissabilité Minimisation
Pour montrer qu’un langage n’est pas reconnaissable, on peut aussi utiliser les
Il y a une infinité d’automates pour un langage donné.
propriétés de clôture.
Exemple : automates D ou ND pour a⇤ .

Exemples : Sachant que L1 n’est pas reconnaissable.
I L 2 \ a ⇤ b⇤ = L 1 .
Questions :
Donc L2 n’est pas reconnaissable.
I Soit f : ⌃⇤ ! ⌃⇤ défini par f (a) = aab et f (b) = abb. I Y a-t-il un automate canonique ?
On a f 1 (L3 ) = L2 . I Y a-t-il unicité d’un automate minimal en nombre d’états ?
Donc L3 n’est pas reconnaissable. I Y a-t-il un lien structurel entre deux automates qui reconnaissent le même
I L5 = {u 2 ⌃⇤ | |u|a 6= |u|b } = L2 . langage ?
Donc L5 n’est pas reconnaissable.
35/197 36/197
Automate des résiduels Congruences et quotients
Définition : Résiduels
Définition : Congruence sur les automates
Soient u 2 ⌃⇤ et L ✓ ⌃⇤ .
Le résiduel de L par u est le quotient u 1 ⇤
L = {v 2 ⌃ | uv 2 L}. Soit A un automate DC. Une relation d’équivalence ⇠ sur Q est une congruence si
I 8p, q 2 Q, 8a 2 ⌃, p ⇠ q implique (p, a) ⇠ (q, a),
Exemple : Calculer les résiduels des langages I F est saturé par ⇠, i.e., 8p 2 F , [p] = {q 2 Q | p ⇠ q} ✓ F .
Pn
Lj = {u = u0 u1 · · · un 2 {0, 1}⇤ | u2 = i
i=0 ui 2 ⌘ j [3]}. Le quotient de A par ⇠ est A/⇠ = (Q/⇠, ⇠ , [i], F/⇠)
où ⇠ est définie par ⇠ ([p], a) = [ (p, a)].
Définition : Automate des résiduels
Soit L ✓ ⌃⇤ . L’automate des résiduels de L est R(L) = (QL , L , iL , FL ) avec Exemple :
1 ⇤
I QL = {u L | u 2 ⌃ },
Donner un automate DCA A à 6 états qui ‘calcule’ u2 mod 3 et accepte L1 .
1 1 1 1
I
L (u L, a) = a (u L) = (ua) L, Exhiber une congruence non triviale sur A.
1 Calculer le quotient A/⇠.
I iL = L = " L,
1 1 1
I FL = {u L|"2u L} = {u L | u 2 L}.
Proposition :
Théorème :
A/⇠ est bien défini et L(A/⇠) = L(A).
Un langage L ✓ ⌃⇤ est reconnaissable ssi L a un nombre fini de résiduels.
37/197 38/197
Équivalence de Nerode Automate minimal

Théorème :
Définition : Équivalence de Nerode
Soit L 2 Rec(⌃⇤ ).
Soit A = (Q, , i, F ) un automate DCA (DC et accessible) reconnaissant L. 1. Si A est un automate DCA qui reconnaı̂t L, alors R(L) est un quotient de A.
Pour q 2 Q, on note L(A, q) = {u 2 ⌃⇤ | (q, u) 2 F }. 2. R(L) est minimal parmi les automates DCA reconnaissant L.
L’équivalence de Nerode de A est définie par p ⇠ q si L(A, p) = L(A, q). (minimal en nombre d’états et minimal pour l’ordre quotient)
3. Soit A un automate DC reconnaissant L avec un nombre minimal d’états.
Proposition : A est isomorphe à R(L) (unicité de l’automate minimal)
L’équivalence de Nerode est une congruence. Corollaire :

L’automate A/⇠ est appelé quotient de Nerode de A. 1. On obtient l’automate minimal de L en calculant le quotient de Nerode de
n’importe quel automate DCA qui reconnaı̂t L.
Théorème : A/⇠ = R(L) 2. Soient A et B deux automates DCA. Pour tester si L(A) = L(B) :
Calculer les quotients de Nerode puis tester leur égalité : A/⇠ = B/⇠.
Le quotient de Nerode est isomorphe à l’automate des résiduels.
' : Q/⇠ ! QL définie par '([q]) = L(A, q) est un isomorphisme de A/⇠ sur R(L).
Problème : comment calculer le quotient de Nerode efficacement ?
39/197 40/197
Algorithme de Moore Logique sur les mots
Pour n 0, on note ⌃n = ⌃0 [ ⌃1 [ · · · [ ⌃n et on définit l’équivalence ⇠n sur
Définition : Syntaxe de MSO(⌃, <)
Q par
p ⇠n q ssi L(A, p) \ ⌃n = L(A, q) \ ⌃n ' ::= ? | Pa (x) | x < y | x 2 X | ¬' | ' _ ' | 9x ' | 9X '
ssi 8w 2 ⌃n , (p, w) 2 F () (q, w) 2 F
avec a 2 ⌃, {x, y, . . .} variables du premier ordre, {X,Y,. . . } variables monadiques
Remarque 1 : ⇠0 a pour classes d’équivalence F et Q \ F . du second ordre.
Remarque 2 : ⇠n+1 est plus fine que ⇠n , i.e., p ⇠n+1 q =) p ⇠n q.
T
Remarque 3 : ⇠ = n 0 ⇠n , i.e., p ⇠ q ssi 8n 0, p ⇠n q. Définition : Sémantique de MSO(⌃, <)
Proposition : Soit A automate DC Soit w = w1 w2 · · · wn 2 ⌃+ un mot et pos(w) = {1, 2, . . . , n} les positions du mot.
Soit une valuation :
I p ⇠n+1 q ssi p ⇠n q et 8a 2 ⌃, (p, a) ⇠n (q, a).
(x) 2 pos(w) si x est une variable du premier ordre et
I Si ⇠n = ⇠n+1 alors ⇠ = ⇠n . (X) ✓ pos(w) si X est une variable monadique du second ordre.
I ⇠ = ⇠|Q| 2 si ; =
6 F 6= Q et ⇠ = ⇠0 sinon.
w, |= Pa (x) si w (x) = a
Permet de calculer l’équivalence de Nerode par raffinements successifs.
w, |= x < y si (x) < (y)
Exercice : w, |= x 2 X si (x) 2 (X)
Calculer l’automate minimal par l’algorithme d’Hopcroft de raffinement de partitions w, |= 9x ' si 9 i 2 pos(w) tel que w, [x 7! i] |= '
en O(n log(n)) (l’algo naı̈f est en O(n2 ) avec n = |Q|). w, |= 9X ' si 9 I ✓ pos(w) tel que w, [X ! 7 I] |= '
41/197 42/197
Logique sur les mots Logique sur les mots

Définition : Codage d’une valuation dans l’alphabet Théorème : Büchi 1960, Elgot 1961, Trakhtenbrot 1961
Soit V un ensemble de variables, on note ⌃V = ⌃ ⇥ {0, 1}V . Un langage L ✓ ⌃+ est reconnaissable si et seulement si il est définissable par une
Un couple (w, ) où w = w1 w2 · · · wn 2 ⌃+ est un mot sur l’alphabet ⌃ et est une formule close ' 2 MSO(⌃, <).
valuation des variables de V est codé par un mot W = (w1 , ⌧1 ) · · · (wn , ⌧n ) 2 ⌃+
V
sur l’alphabet ⌃V avec: Preuve
I 8i 2 pos(w), ⌧i (x) = 1 ssi (x) = i =) : Si L est reconnu par un automate A ayant n états Q = {q1 , . . . , qn }, on écrit
si x 2 V est une variable du premier ordre, une formule de la forme ' = 9X1 · · · 9Xn (X1 , . . . , Xn ) qui caractérise l’existence
d’un calcul acceptant de A sur un mot w 2 ⌃+ .
I 8i 2 pos(w), ⌧i (X) = 1 ssi i 2 (X)
Xi est l’ensemble des positions de w pour lesquelles le calcul est dans l’état qi .
si X 2 V est une variable monadique du second ordre.
La formule assure que les transitions de l’automate sont respectées.
Un mot W 2 ⌃+
V est valide si il code un couple (w, ). On identifie W et (w, ).
(= : On donne des expressions rationnelles pour les formules atomiques.
Définition : Sémantique de MSO(⌃, <) On note ⌃x=1V = {(a, ⌧ ) 2 ⌃V | ⌧ (x) = 1}, de même ⌃x=0 V ou ⌃X=1
V ou ⌃X=0
V .
⇤ x=0 ⇤
LV (Pa (x)) = (⌃x=0
V ) (⌃ x=1
V \ ({a} ⇥ {0, 1} V
))(⌃ V ) .
Soit ' 2 MSO(⌃, <) et soit V un ensemble de variables contenant les variables LV (x 2 X) = (⌃x=0 ⇤ x=1
\ ⌃X=1 )(⌃x=0 ⇤
V ) (⌃V V V ) .
libres de ', LV (x < y) = (⌃x=y=0 )⇤ (⌃x=1 \ ⌃y=0 x=y=0 ⇤
) (⌃x=0 \ ⌃y=1 x=y=0 ⇤
) .
V V V )(⌃V V V )(⌃V
On utilise les propriétés de clôture des langages reconnaissables :
LV (') = {W 2 ⌃+
V | W = (w, ) est valide et (w, ) |= '} union (_), complémentaire (¬) et projection (9x et 9X).
43/197 44/197
Morphismes Morphismes
Définition : Reconnaissance par morphisme Théorème :
I ' : ⌃⇤ ! M morphisme dans un monoı̈de fini M . Soit L ✓ ⌃⇤ . L est reconnaissable par morphisme ssi L est reconnaissable par
L ✓ ⌃⇤ est reconnu ou saturé par ' si L = ' 1 ('(L)). automate.
I L ✓ ⌃⇤ est reconnu par un monoı̈de fini M s’il existe un morphisme
' : ⌃⇤ ! M qui reconnaı̂t L. Corollaire :
I ⇤
L ✓ ⌃ est reconnaissable par morphisme s’il existe un monoı̈de fini qui Rec(⌃⇤ ) est fermée par morphisme inverse.
reconnaı̂t L.
Exemple :
Définition : Monoı̈de de transitions p
Si L est reconnaissable alors L = {v 2 ⌃⇤ | v 2 2 L} est aussi reconnaissable.
Soit A = (Q, ⌃, , i, F ) un automate déterministe complet.
Le monoı̈de de transitions de A est le sous monoı̈de de (QQ , ⇤) engendré par les Exercices :
applications a : Q ! Q (a 2 ⌃) définies par a (q) = (q, a) et avec la loi de
1. Montrer que Rec(⌃⇤ ) est fermée par union, intersection, complémentaire.
composition interne f ⇤ g = g f .
2. Montrer que Rec(⌃⇤ ) est fermée par quotients.
Proposition : Si L 2 Rec(⌃⇤ ) et K ✓ ⌃⇤ alors K 1 L et LK 1
sont reconnaissables.
⇤
Le monoı̈de de transitions de A reconnaı̂t L(A). 3. Montrer que Rec(⌃ ) est fermée par concaténation (plus difficile).
45/197 46/197
Congruences Morphismes et Congruences

Exercice :
Définition :
Soit L un langage reconnaissable. Montrer que le langage
Soit L ✓ ⌃⇤ et ⌘ une congruence sur ⌃⇤ .
Le langage L est saturé par ⌘ si 8u, v 2 ⌃⇤ , u ⌘ v implique u 2 L () v 2 L. L0 = {v 2 ⌃⇤ | v |v| 2 L}
Théorème : est aussi reconnaissable.

Soit L ✓ ⌃⇤ . L est reconnaissable ssi L est saturé par une congruence d’index fini.
Exercice : Machine de Turing et automates
Exemple : Automate à double sens (Boustrophédon) Une machine de Turing qui ne modifie pas sa donnée est une MT à une seule bande
Un automate Boustrophédon est un automate fini non déterministe qui, à chaque qui ne peut pas modifier le mot d’entrée, mais qui peut bien sûr écrire sur sa bande
transition, peut déplacer sa tête de lecture vers la droite ou vers la gauche. en dehors de la zone occupée par le mot d’entrée. La MT peut être non déterministe
De façon équivalente, c’est une machine de Turing à une seule bande qui n’écrit pas et ne s’arrête pas forcément.
sur cette bande. 1. Montrer qu’une MT qui ne modifie pas sa donnée reconnaı̂t en fait un langage
1. Montrer que tout langage accepté par un automate Boustrophédon est en fait rationnel.
rationnel. 2. Étant donnée une MT qui ne modifie pas sa donnée, montrer que l’on peut
2. Montrer qu’à partir d’un automate Boustrophédon ayant n états, on peut e↵ectivement calculer la fonction de transition d’un automate fini déterministe
e↵ectivement construire un automate déterministe classique équivalent ayant équivalent.
2
2O(n ) états. 3. Peut-on décider le problème du mot pour une MT qui ne modifie pas sa
donnée ?
47/197 48/197
Congruence et monoide syntaxique Congruences
Définition : Congruence syntaxique
Soit L ✓ ⌃⇤ . u ⌘L v si 8x, y 2 ⌃⇤ , xuy 2 L () xvy 2 L.
Théorème :
Soit L ✓ ⌃⇤ .
Exercice : Congruence à droite
I ⌘L est une congruence et ⌘L sature L.
1. Montrer que L ✓ ⌃⇤ est reconnaissable ssi il est saturé par une congruence à
I ⌘L est la plus grossière congruence qui sature L. droite d’index fini
I L est reconnaissable ssi ⌘L est d’index fini. 2. Soit u ⌘rL v si 8y 2 ⌃⇤ , uy 2 L () vy 2 L.
Montrer que ⌘rL est la congruence à droite la plus grossière qui sature L.
Définition : Monoide syntaxique
3. Faire le lien entre ⌘rL et l’automate minimal de L
Soit L ✓ ⌃⇤ . ML = ⌃⇤ / ⌘L .
Théorème :
Soit L ✓ ⌃⇤ .
I ML est le monoı̈de de transitions de l’automate minimal de L.
I ML divise (est quotient d’un sous-monoı̈de) tout monoı̈de qui reconnaı̂t L.
On peut e↵ectivement calculer le monoı̈de syntaxique d’un langage reconnaissable.
49/197 50/197
Apériodiques et sans étoile Sans étoile et sans compteur

Définition : Sans étoile
La famille des langages sans étoile est la plus petite famille qui contient les langages
finis et qui est fermée par union, concaténation et complémentaire. Définition : Compteur
Exemple : Le langage (ab)⇤ est sans étoile. Soit A = (Q, ⌃, , i, F ) un automate déterministe complet.
L’automate A est sans compteur si
Définition : Apériodique
I Un monoı̈de fini M est apériodique si il existe n 0 tel que pour tout x 2 M 8w 2 ⌃⇤ , 8m 1, 8p 2 Q, (p, wm ) = p ) (p, w) = p .
on a xn = xn+1 . Exemple : L’automate minimal de (aa)⇤ possède un compteur.
I Un langage est apériodique s’il peut être reconnu par un monoı̈de apériodique.
I Rem: L est apériodique si et seulement si ML est fini et apériodique. Théorème : Mc Naughton, Papert 1971
Un langage est sans étoile si et seulement si son automate minimal est sans compteur.
Théorème : Schützenberger 1965
Un langage est sans étoile si et seulement si son monoı̈de syntaxique est apériodique. Exercice :
Montrer que le langage ((a + cb⇤ a)c⇤ b)⇤ est sans étoile.
Exemple : Le langage (aa)⇤ n’est pas sans étoile.
Exercice :
Montrer que le langage ((a + cb⇤ a)c⇤ b)⇤ est sans étoile.
51/197 52/197
Sans étoile et logique du premier ordre Plan
Introduction
Théorème : Mc Naughton, Papert 1971
Un langage L ✓ ⌃+ est sans étoile si et seulement si il est définissable par une
formule de la logique du premier ordre FO(⌃, <).
3 Automates d’arbres
Exemple : Le langage (aa)⇤ n’est pas définissable en FO(⌃, <). Arbres
Exercice : Automates d’arbres
Termes
Montrer que le langage ((a+cb⇤ a)c⇤ b)⇤ est définissable en logique du premier ordre:
FO(⌃, <). Ascendant / Descendant
Déterminisme
Théorème : Lemme d’itération
Un langage L ✓ ⌃+ est sans étoile si et seulement si il est définissable par une Congruences
formule ' 2 FO3 (⌃, <) qui utilise au plus 3 noms de variables. Minimalité
Logique MSO
Exercice :
Montrer que ((a + cb⇤ a)c⇤ b)⇤ est définissable par une formule de FO3 (⌃, <). Grammaires
53/197 Langages algébriques 54/197
Automates à pile
Bibliographie Analyse syntaxique Arbres

Définition : Arbres
Fonctions
Soit Ap = {d1séquentielles
, . . . , dp } un alphabet ordonné d1 ··· dp .
Un arbre fini sur l’alphabet ⌃ et d’arité (au plus) p est une fonction partielle
t : A⇤p ! ⌃ dont le domaine est un langage fini non vide ; =
6 dom(t) ✓ A⇤p
I fermé par préfixe : u  v et v 2 dom(t) implique u 2 dom(t),
[8] Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis I fermé par frère aı̂né : di dj et udj 2 dom(t) implique udi 2 dom(T ).
Lugiez, Sophie Tison, Marc Tommasi. On note Tp (⌃) l’ensemble des ⌃-arbres finis d’arité au plus p.
Tree Automata Techniques and Applications.
http://www.grappa.univ-lille3.fr/tata/
Exemples :
1. Arbre représentant l’expression logique
((x ! y) ^ (¬y _ ¬z)) ^ (z _ ¬x)
2. Arbre représentant le programme

lire a; lire b; q := 0; r := a;
Tant que b  r faire q := q+1; r := r-b Fin tant que;
afficher q; afficher r.
55/197 56/197
Arbres Automates d’arbres
Définition : Terminologie
Définition : Automate
La racine de l’arbre est le mot vide " 2 dom(t).
Un nœud de l’arbre est un élément u 2 dom(t). Un automate d’arbres est un quadruplet A = (Q, ⌃, , F ) où
Une feuille de l’arbre est un nœud u 2 dom(t) tel que ud1 2
/ dom(t). I Q est un ensemble fini d’états
Le nombre de nœuds (taille) de l’arbre est |t| = |dom(t)|. I ⌃ est un alphabet fini
La hauteur de l’arbre est H(t) = max{|u| | u 2 dom(t)}. S
I ✓ n Qn ⇥ ⌃ ⇥ Q est l’ensemble fini des transitions
La frontière Fr(t) de l’arbre t est la concaténation des étiquettes des feuilles de t. I F ✓ Q est l’ensemble des états finaux.
L’arité d’un nœud u 2 dom(t) est max{n | udn 2 dom(t)} (max ; = 0).
L’arité d’une feuille est 0. Définition : Calcul, langage
Les fils d’un nœud u 2 dom(t) d’arité n sont les nœuds ud1 , . . . , udn 2 dom(t). I Un calcul de l’automate A sur un arbre t 2 Tp (⌃) est un arbre ⇢ 2 Tp (Q)
ayant même domaine que t et tel que pour tout u 2 dom(t) d’arité n, on a
Définition inductive de Tp (⌃) (notation préfixe) (⇢(u · d1 ), . . . , ⇢(u · dn ), t(u), ⇢(u)) 2 .
Si a 2 ⌃ alors t = a 2 Tp (⌃) : dom(t) = {"} et t(") = a I Le calcul est acceptant si ⇢(") 2 F .
Si a 2 ⌃ et t1 , . . . , tn 2 Tp (⌃) avec 1  n  p alors t = a(t1 , . . . , tn ) 2 Tp (⌃) : I L(A) est l’ensemble des ⌃-arbres acceptés par A.
Sn
I dom(t) = {"} [
i=1 di dom(ti ), I Un langage d’arbre est reconnaissable s’il existe un automate d’arbres qui
I t(") = a et la racine de t est d’arité n, l’accepte.
I t(di v) = ti (v) pour 1  i  n et v 2 dom(ti ).
57/197 58/197
Automates d’arbres Grammaires et automates d’arbres
Exemples : Donner des automates pour les langages d’arbres suivants :

1. L’ensemble des arbres d’arité au plus p ayant un nombre pair de nœuds
internes.
2. L = {tn | n > 0} avec t1 = c(a, b) et tn+1 = c(a, tn , b). Théorème : du feuillage
3. L’ensemble des arbres de la forme t = f (g(t1 ), f (t2 , a)) 2 Tp (⌃). I Soit L un langage d’arbres reconnaissable.
⇤ Le langage Fr(L) des frontières des arbres de L est algébrique.
4. Soit ⌃ = {a, b, c}. L’ensemble des arbres t 2 T2 (⌃) tels que Fr(t) 2 (ab) et
dont les nœuds internes sont d’arités 2 et étiquetés par c. I Soit L0 un langage algébrique propre (" 2
/ L0 ).
Il existe un langage d’arbres reconnaissable L tel que L0 = Fr(L).
5. Généraliser à un langage reconnaissable arbitraire pour la frontière.
6. L’ensemble des arbres d’arité au plus p dont les étiquettes de toutes les
branches sont dans un langage rationnel fixé L ✓ ⌃⇤ .
7. L’ensemble des arbres d’arité au plus p dont au moins une branche est
étiquetée par un mot d’un langage rationnel fixé L ✓ ⌃⇤ .
59/197 60/197
Termes Termes
Définition : Un terme est un arbre avec symboles typés
I F un ensemble fini de symboles de fonctions avec arités.
I On note Fn les symboles d’arité n. Exemple : Expressions logiques
I X un ensemble de variables (arité 0) disjoint de F0 (les constantes). F2 = {^, _, !, , . . .}, F1 = {¬}, F0 = {>, ?}, X = {p, q, r}
I T (F, X ) ensemble des termes sur F et X défini inductivement par :
I F0 [ X ✓ T (F , X ), ^(_(¬(p), q), _(¬(q), r)) = (¬p _ q) ^ (¬q _ r)
I si f 2 Fn (n 1) et t1 , . . . , tn 2 T (F , X ) alors f (t1 , . . . , tn ) 2 T (F , X )
Remarque : on peut aussi utiliser une notation suffixe ou infixe parenthésée. Exemple : Expressions arithmétiques
I Free(t) est l’ensemble des variables de t. F2 = {+, , ⇥, /, . . .}, F1 = {sin, cos, ln, !, . . .},
I T (F) l’ensemble des termes qui ne contiennent pas de variable (termes clos). F0 = {0, . . . , 9} et X = {x, y, . . .}.
I Un terme t est linéaire s’il contient au plus une occurrence de chaque variable.
+(3, ⇥(2, !(x))) = 3 + (2 ⇥ x!)
I Hauteur : H(x) = 0 pour x 2 X et H(f ) = 0 pour f 2 F0 et
H(f (t1 , . . . , tn )) = 1 + max(H(t1 ), . . . , H(tn )).
I Taille : |x| = 0 pour x 2 X et |f | = 1 pour f 2 F0 et
|f (t1 , . . . , tn )| = 1 + |t1 | + · · · + |tn |.
61/197 62/197
Arbres et termes Arbres et termes

Un terme est un arbre typé
Un terme peut être vu comme un arbre t étiqueté dans F [ X tel que Un arbre est la projection d’un terme clos
I si u 2 dom(t) et t(u) 2 Fn alors u est d’arité n.
Soit t 2 Tp (⌃) un ⌃-arbre d’arité au plus p.
I si u 2 dom(t) et t(u) 2 X alors u est une feuille.
Soit F = ⌃ ⇥ {0, . . . , p} avec Fi = ⌃ ⇥ {i} pour 0  i  p.
La hauteur d’un terme clos est la hauteur de l’arbre qui le représente.
La taille d’un terme clos est le nombre de nœuds de l’arbre qui le représente. Soit t0 l’arbre ayant même domaine que t et tel que si u 2 dom(t) est d’arité i et
t(u) = f alors t0 (u) = (f, i).
Exemples : t0 2 T (F) est un terme clos et t est le projeté de t0 .
1. Soit F un ensemble fini de symboles de fonctions avec arités et X un
ensemble fini de variables. Le langage d’arbres T (F, X ) est reconnaissable. Remarque :
2. Considérons F2 = {^, _}, F1 = {¬}, F0 = {>, ?} et X = ;. Un arbre de dérivation n’est pas toujours un terme car les règles associées à une
L’ensemble des formules closes du calcul propositionnel qui s’évaluent à vrai variable n’ont pas forcément une longueur fixe.
est reconnaissable.
Exemple : S ! aSb + ab
3. Considérons F2 = {^, _}, F1 = {¬}, F0 = {>, ?} et X = {p1 , . . . , pn } fini.
L’ensemble des formules satisfaisables du calcul propositionnel est
reconnaissable.
63/197 64/197
Vision ascendante Vision descendante
Définition : calcul descendant
Définition : calcul ascendant Soit A = (Q, ⌃, , I) un automate d’arbres. S
n
Soit A = (Q, ⌃, , F ) un automateSd’arbres. On voit comme une fonction : Q ⇥ ⌃ ! 2 n Q .
On voit comme une fonction : n Qn ⇥ ⌃ ! 2Q . L’étiquetage d’un calcul est construit à partir de la racine en descendant vers les
L’étiquetage d’un calcul est construit à partir des feuilles en remontant vers la racine. feuilles.
L’étiquette de la racine doit être dans I.
Exemples : On dit que I est l’ensemble des états initiaux.
1. Évaluation d’une formule close du calcul propositionnel. Exemples :
2. Arbres de la forme t = f (g(t1 ), f (t2 , a)) 2 Tp (⌃).
1. Arbres de la forme t = f (g(t1 ), f (t2 , a)) 2 Tp (⌃).
Définition : Déterminisme ascendant 2. Évaluation d’une formule close du calcul propositionnel.
S n
Un automate A = (Q, ⌃, , F ) est déterministe ascendant si : Q ⇥⌃ ! Q
n Définition : Déterminisme descendant
est une fonction (partielle si A n’est pas complet).
Un automate A = (Q, ⌃, , I) est déterministe descendant s’il a un seul état initial
Exercice : et si pour tous q 2 Q, a 2 ⌃ et n 0 on a | (q, a) \ Qn |  1.
Parmi les automates d’arbres vus précédemment, quels sont ceux qui sont
Exercice :
déterministes ascendants ?
Parmi les automates d’arbres vus précédemment, quels sont ceux qui sont
déterministes descendants ?
65/197 66/197
Automates déterministes Substitutions d’arbres

Définition :
I Une substitution est une application d’un sous-ensemble fini de X dans
Théorème : Déterminisation Tp (⌃ [ X ).
Soit A un automate d’arbres. On peut e↵ectivement construire un automate I Si = [t1 /x1 , . . . , tn /xn ] est une substitution et t un arbre alors
déterministe ascendant B tel que L(A) = L(B). (t) = t[t1 /x1 , . . . , tn /xn ] est défini inductivement par :
I (xi ) = ti pour 1  i  n (feuille étiquetée par une variable à substituer),
I (f ) = f pour f 2 ⌃ [ X \ {x1 , . . . , xn } (autre feuille),
Théorème : Clôture
I (f (s1 , . . . , sk )) = f ( (s1 ), . . . , (sk )) pour f 2 ⌃ (nœud interne).
La classe des langages d’arbres reconnaissables est e↵ectivement close par union,
On dit que t[t1 /x1 , . . . , tn /xn ] est une instance de t.
intersection et complémentaire.
I La substitution = [t1 /x1 , . . . , tn /xn ] est close si chaque ti est clos.
Proposition : I Si t1 , t2 sont clos, alors t[t1 /x1 , t2 /x2 ] = t[t1 /x1 ][t2 /x2 ].
La classe des langages d’arbres reconnaissables par un automate déterministe descen- En général, t[t1 /x1 , t2 /x2 ] 6= t[t1 /x1 ][t2 /x2 ].
dant est strictement incluse dans la classe des langages d’arbres reconnaissables.
Exemple : le langage {f (a, b), f (b, a)} n’est pas déterministe descendant. Exemple : Instances d’un terme
Soit s = f (g(x), f (y, a)) 2 T (F, X ).
L’ensemble des termes t 2 T (F) qui sont instances de s est reconnaissable.
Généraliser à l’ensemble des instances d’un ensemble fini de termes linéaires.
67/197 68/197
Concaténation d’arbres Lemme d’itération
Lemme : itération (pumping)
Définition : Arbre à trou ou contexte
Soit L un langage d’arbres reconnaissable.
Un ⌃-arbre à trou t est un (⌃ [ {2})-arbre ayant un unique nœud étiqueté 2 et ce 9n > 0, 8t 2 L, si H(t) n alors 9t1 , t2 2 T2 (⌃), 9t3 2 T (⌃) tels que
nœud doit être une feuille : t : A⇤p ! ⌃ [ {2}, t 1 (2) = {u} et ud1 2
/ dom(t). I t2 6= 2, t = t1 · t2 · t3 , t1 (t2 )⇤ t3 ✓ L,
On note Tp,2 (⌃) l’ensemble des ⌃-arbres à trou d’arité au plus p.
I prof 2 (t1 ) + prof 2 (t2 )  n ou prof 2 (t2 ) + H(t3 )  n.
Définition : Concaténation prof 2 (2) = 0, prof 2 (a) = 1,
0
Soit t 2 T2 (⌃) et soit t 2 T (⌃) [ T2 (⌃). prof 2 (a(t1 , . . . , tn )) = 1 + max(prof 2 (t1 ), . . . , prof 2 (tn )).
La concaténation t · t0 = t[t0 /2] est le ⌃-arbre (avec ou sans trou) obtenu en Exemples :
appliquant la substitution [t0 /2] à l’arbre t. I L = {f (g n (a), g m (a)) | n, m 0} est reconnaissable.
L’ensemble T2 (⌃) est un monoı̈de avec comme élément neutre 2. I L = {f (g n (a), g n (a)) | n 0} n’est pas reconnaissable.
I L’ensemble des instances de f (x, x) n’est pas reconnaissable.
Exemple :
I Associativité. Soit F2 = {f } et F0 = {a, b}.
Soient t1 = c(a, 2, b) et t2 = c(a, b). Un langage L ✓ T (F) est associativement clos si il est fermé par la
Le langage L = t⇤1 t2 est reconnaissable. congruence engendrée par f (f (x, y), z) = f (x, f (y, z)).
Remarque : le langage Fr(L) des mots de feuilles de L est {an bn | n > 0}. Soit t1 = f (f (a, 2), b) et t2 = f (a, b).
t⇤1 t2 est reconnaissable mais sa clôture associative n’est pas reconnaissable.
69/197 70/197
Congruences Congruence syntaxique

Définition : Résiduels et Congruence syntaxique
Soit L ✓ Tp (⌃) un langage d’arbres et s 2 Tp (⌃). Le résiduel de L par s est
L\s = {r 2 Tp,2 (⌃) | r · s 2 L}.

Définition : Congruence (en haut)
Une relation d’équivalence ⌘ sur Tp (⌃) est une congruence si pour tous a 2 ⌃, et La congruence syntaxique ⌘L associée à L est définie par s ⌘L t si L\s = L\t.
t1 , . . . , tn , s1 , . . . , sn 2 Tp (⌃) avec n  p on a
Remarque :
(81  i  n, si ⌘ ti ) =) a(s1 , . . . , sn ) ⌘ a(t1 , . . . , tn ) La relation d’équivalence ⌘L est bien une congruence et sature le langage L.
⌘L est la plus grossière congruence qui sature L.
Proposition :
Une relation d’équivalence ⌘ sur Tp (⌃) est une congruence si et seulement si pour Lemme :
tout r 2 Tp,2 (⌃) et tous s, t 2 Tp (⌃), on a s ⌘ t implique r · s ⌘ r · t.
Soit A = (Q, ⌃, , F ) un automate DC (déterministe, complet) reconnaissant L.
Pour t 2 Tp (⌃), on note A(t) l’état à la racine du run de A sur t.
La relation ⌘A sur Tp (⌃) est définie par s ⌘A t si A(s) = A(t).
⌘A est une congruence qui sature L.
Donc ⌘A et ⌘L sont d’index finis.
71/197 72/197
Congruence et reconnaissabilité Equivalence de Nerode
Définition :
Soit ⌘ une congruence d’index fini qui sature L ✓ Tp (⌃).
On note [t] la classe pour ⌘ d’un arbre t 2 Tp (⌃). Définition : Equivalence de Nerode
On définit l’automate A⌘ = (Q, ⌃, , F ) par : Soit A = (Q, ⌃, , F ) un automate DAC reconnaissant L ✓ Tp (⌃).
I Q = Tp (⌃)/⌘, Pour q 2 Q, on note Aq = (Q, ⌃ ] {2}, ] {(2, q)}, F ).
I ([t1 ], . . . , [tn ], a) = [a(t1 , . . . , tn )] (bien définie car ⌘ congruence), On note L2 (Aq ) = Tp,2 (⌃) \ L(Aq ).
I F = {[t] | t 2 L}. L’équivalence de Nerode de l’automate A est définie par
Pour la congruence syntaxique, on note simplement AL = (QL , ⌃, L , FL ) = A⌘L . q ⇠ q 0 si L2 (Aq ) = L2 (Aq0 ).
Lemme : Lemme : Equivalence de Nerode et congruence syntaxique

L’automate A⌘ est DAC (déterministe, accessible, complet) et reconnaı̂t L.
I ⇠ est une relation d’équivalence qui sature F .
Théorème : Myhill-Nerode I Soit t 2 Tp (⌃) et q = A(t). On a L\t = L2 (Aq )
Soit L ✓ Tp (⌃). Les conditions suivantes sont équivalentes :
I Soient t, t0 2 Tp (⌃), q = A(t) et q 0 = A(t0 ). On a q ⇠ q 0 () t ⌘L t0
1. L est reconnaissable,
2. L est saturé par une congruence d’index fini,
3. la congruence syntaxique ⌘L est d’index fini.
73/197 74/197
Automate minimal Calcul de l’équivalence de Nerode

Proposition :
Soit A = (Q, ⌃, , F ) un automate DAC reconnaissant L ✓ Tp (⌃).
Définition : Quotient de Nerode
On définit les relations d’équivalence (⇠m )m 0 inductivement :
Soit A = (Q, ⌃, , F ) un automate DAC reconnaissant L ✓ Tp (⌃).
On définit le quotient de Nerode A/⇠ = (Q/⇠, ⌃, ⇠ , F/⇠) avec I q ⇠0 q 0 si q, q 0 2 F ou q, q 0 2
/F
⇠ ([q1 ], . . . , [qn ], a) = [ (q1 , . . . , qn , a)]
I q ⇠m+1 q 0 si q ⇠m q 0 et 8a 2 ⌃ et 8q1 , . . . , qi 1 , qi+1 , . . . , qn 2 Q on a
(q1 , . . . , qi 1 , q, qi+1 , . . . , qn , a) ⇠m (q1 , . . . , qi 1 , q 0 , qi+1 , . . . , qn , a)
La fonction de transition ⇠ est bien définie.
On a alors \
Théorème : automate minimal ⇠= ⇠m = ⇠|Q|
Soit A = (Q, ⌃, , F ) un automate DAC reconnaissant L ✓ Tp (⌃). m 0
1. AL est isomorphe au quotient de Nerode A/⇠.

2. Si A a un nombre minimal d’états alors AL est isomorphe à A. Plus précisément, on note
m
3. AL est l’unique à isomorphisme près automate DAC minimal reconnaissant L. Tp,2 (⌃) = {r 2 Tp,2 (⌃) | prof 2 (t)  m} et Lm m
2 (Aq ) = Tp,2 (⌃) \ L(Aq )
On a
q ⇠m q 0 () Lm m
2 (Aq ) = L2 (Aq 0 )
75/197 76/197
Exercices Logique sur les arbres
Définition : Syntaxe de MSO(⌃, #1 , . . . , #p )
' ::= ? | Pa (x) | x #1 y | · · · | x #p y | x 2 X | ¬' | ' _ ' | 9x ' | 9X '
avec a 2 ⌃, {x, y, . . .} variables du premier ordre, {X,Y,. . . } variables monadiques
Exercice : Morphisme du second ordre.
Montrer que L ✓ T (F) est reconnaissable ssi il existe une F-algèbre finie A(F)
telle que L = ' 1 ('(L)) où ' : T (F) ! A(F) est le morphisme canonique. Définition : Sémantique de MSO(⌃, #1 , . . . , #p )
Soit t : A⇤p ! ⌃ un ⌃-arbre d’arité au plus p.
Exercice : Problèmes de décision et complexité Soit une valuation :
Lire la section 7 du chapitre 1 du TATA. (x) 2 dom(t) si x est une variable du premier ordre et
(X) ✓ dom(t) si X est une variable monadique du second ordre.
t, |= Pa (x) si t( (x)) = a
t, |= x #i y si (y) = (x) · di
t, |= x 2 X si (x) 2 (X)
t, |= 9x ' si 9 u 2 dom(t) tel que t, [x 7! u] |= '
t, |= 9X ' si 9 U ✓ dom(t) tel que t, [X ! 7 U ] |= '
77/197 78/197
Logique sur les arbres Logique sur les arbres

Définition : Codage d’une valuation dans l’alphabet
Soit V un ensemble de variables, on note ⌃V = ⌃ ⇥ {0, 1}V .
Exemples : Un couple (t, ) où t : A⇤p ! ⌃ est un ⌃-arbre d’arité au plus p et est une valuation
des variables de V est codé par un ⌃V -arbre T = (t, ⌧ ) : A⇤p ! ⌃V sur l’alphabet
I L’ensemble des arbres d’arité au plus p ayant un nombre pair de nœuds
⌃V avec:
internes.
I 8u 2 dom(t), ⌧ (u)(x) = 1 ssi (x) = u
I L’ensemble des formules closes du calcul propositionnel qui s’évaluent à vrai
si x 2 V est une variable du premier ordre,
est définissable en MSO(⌃, #1 , #2 ).
I 8u 2 dom(t), ⌧ (u)(X) = 1 ssi u 2 (X)
Exercice : ordre ascendant si X 2 V est une variable monadique du second ordre.
On considère la relation d’ordre “être un ascendant”, i.e., x < y si le nœud x est Un ⌃V -arbre T est valide si il code un couple (t, ). On identifie T et (t, ).
un ascendant du nœud y.
Montrer que cette relation est définissable en MSO(⌃, #1 , . . . , #p ). Définition : Sémantique de MSO(⌃, #1 , . . . , #p )
Soit ' 2 MSO(⌃, #1 , . . . , #p ) et soit V un ensemble de variables contenant les
variables libres de ',
LV (') = {T 2 Tp (⌃V ) | T = (t, ) est valide et (t, ) |= '}
79/197 80/197
Logique sur les arbres Plan
Introduction
Théorème : Thatcher and Wright 1968 Langages reconnaissables

Un langage L ✓ Tp (⌃) est reconnaissable si et seulement si il est définissable par
une formule close ' 2 MSO(⌃, #1 , . . . , #p ). Automates d’arbres
Preuve 4 Grammaires
=) : Si L est reconnu par un automate A ayant n états Q = {q1 , . . . , qn }, on écrit Type 0 : générale
une formule de la forme ' = 9X1 · · · 9Xn (X1 , . . . , Xn ) qui caractérise l’existence Type 1 : contextuelle (context-sensitive)
d’un calcul acceptant de A sur un arbre t 2 Tp (⌃). Type 2 : hors contexte (context-free, algébrique)
Xi est l’ensemble des nœuds de t pour lesquels le calcul est dans l’état qi . Grammaires linéaires
La formule assure que les transitions de l’automate sont respectées.
Hiérarchie de Chomsky
(= : On construit facilement des automates pour les formules atomiques.
On utilise les propriétés de clôture des langages reconnaissables : Langages algébriques
union (_), complémentaire (¬) et projection (9x et 9X).
Automates à pile
81/197 Analyse syntaxique 82/197
Grammaires de type 0 Grammaires de type 0
Définition : Grammaires générales (type 0)
G = (⌃, V, P, S) où
I ⌃ est l’alphabet terminal
Définition : Langage engendré
I V est l’alphabet non terminal (variables)
Soit G = (⌃, V, P, S) une grammaire et ↵ 2 (⌃ [ V )⇤ .
I S 2 V est l’axiome (variable initiale) ⇤
Le langage engendré par ↵ est LG (↵) = {u 2 ⌃⇤ | ↵ ! u}.
I P ✓ (⌃ [ V )⇤ ⇥ (⌃ [ V )⇤ est un ensemble fini de règles ou productions. b ⇤
Le langage élargi engendré par ↵ est LG (↵) = { 2 (⌃ [ V )⇤ | ↵ ! }.
n Le langage engendré par G est LG (S).
Exemple : Une grammaire pour {a2 | n > 0} Un langage est de type 0 s’il peut être engendré par une grammaire de type 0.
1: S ! DXaF 3 : XF ! Y F 5 : DY ! DX 7 : aZ ! Za Théorème : Type 0 [9, Thm 9.3 & 9.4]

2 : Xa ! aaX 4 : aY ! Y a 6 : XF ! Z 8 : DZ ! "
Un langage L ✓ ⌃⇤ est de type 0 ssi il est récursivement énumérable.
Définition : Dérivation
↵ 2 (⌃ [ V )⇤ se dérive en 2 (⌃ [ V )⇤ , noté ↵ ! , s’il existe (↵2 , 2) 2 P tel
que ↵ = ↵1 ↵2 ↵3 et = ↵1 2 ↵3 .
⇤
On note ! la clôture réflexive et transitive de !.
83/197 84/197
Grammaires contextuelles Grammaires contextuelles
Définition : Grammaire contextuelle (type 1, context-sensitive) Définition : Forme normale (context-sensitive/contextuelle)

Une grammaire G = (⌃, V, P, S) est contextuelle si toute règle (↵, ) 2 P vérifie Une grammaire G = (⌃, V, P, S) contextuelle est en forme normale si toute règle
|↵|  | |. est de la forme (↵1 X↵2 , ↵1 ↵2 ) avec X 2 V et 6= ".
Un langage est de type 1 (ou contextuel) s’il peut être engendré par une grammaire
contextuelle. Théorème : Forme normale [4, Prop. 2, p. 156]
2n Tout langage de type 1 est engendré par une grammaire contextuelle en forme
Exemple : Une grammaire contextuelle pour {a | n > 0}
normale.
1 : S ! DT F 3 : T ! XT 5 : Xaa ! aaXa 7 : Daaa ! aaDaa n
2 : S ! aa 4 : T ! aa 6 : XaF ! aaF 8 : DaaF ! aaaa

Exemple : Une grammaire contextuelle en FN pour {a2 | n > 0}
1 : S ! aT a 3 : T ! XT 5 : XA ! XY 8 : Xa ! AAa
Remarque :
2 : S ! aa 4 : T ! AA 6 : XY ! ZY 9 : ZA ! AAA
Le langage engendré par une grammaire contextuelle est propre.
7 : ZY ! ZX 10 : aA ! aa
Si on veut engendrer le mot vide on peut ajouter Ŝ ! S + ".
85/197 86/197
Grammaires contextuelles Grammaires algébriques

Théorème : Type 1 [9, Thm 9.5 & 9.6] Définition : Grammaire hors contexte ou algébrique ou de type 2
Un langage est de type 1 ssi il est accepté par une machine de Turing non déterministe Une grammaire G = (⌃, V, P, S) est hors contexte ou algébrique si P ✓ V ⇥(⌃[V )⇤
en espace linéaire. (sous ensemble fini).
Les langages contextuels sont strictement inclus dans les langages récursifs. Un langage est de type 2 (ou hors contexte ou algébrique) s’il peut être engendré
par une grammaire hors contexte.
Théorème : Problème du mot
On note Alg la famille des langages algébriques.
Étant donnés un mot w et une grammaire G, décider si w 2 LG (S).
Le problème du mot est décidable en PSPACE pour les grammaires de type 1. Exemples :
Théorème : indécidabilité du vide 1. Le langage {an bn | n 0} est algébrique.
On ne peut pas décider si une grammaire contextuelle engendre un langage vide. 2. Expressions complètement parenthésées.
Exercices : Lemme : fondamental

2
1. Montrer que {an | n > 0} est contextuel. Soit G = (⌃, V, P, S) une grammaire algébrique, ↵1 , ↵2 , 2 (⌃ [ V )⇤ et n 0.
2. Montrer que {ww | w 2 {a, b}+ } est contextuel. n 1n n2
↵1 ↵2 ! () ↵1 ! 1 , ↵2 ! 2 avec = 1 2 et n = n1 + n2
87/197 88/197
Langages de Dyck Grammaires linéaires
Définition : Dn⇤ Définition : Grammaire linéaire
La grammaire G = (⌃, V, P, S) est
Soit ⌃n = {a1 , . . . , an } [ {ā1 , . . . , ān } l’alphabet formé de n paires de parenthèses.
Soit Gn = (⌃n , V, Pn , S) la grammaire définie par S ! a1 Sā1 S +· · ·+an Sān S +". I linéaire si P ✓ V ⇥ (⌃⇤ [ ⌃⇤ V ⌃⇤ ),
Le langage Dn⇤ = LGn (S) est appelé langage de Dyck sur n paires de parenthèses I linéaire gauche si P ✓ V ⇥ (⌃⇤ [ V ⌃⇤ ),
I linéaire droite si P ✓ V ⇥ (⌃⇤ [ ⌃⇤ V ).
Exercices : Langages de Dyck
Un langage est linéaire s’il peut être engendré par une grammaire linéaire.
1. Montrer que
D1⇤ = {w 2 ⌃⇤1 | |w|a1 = |w|ā1 et |v|a1 |v|ā1 pour tous v  w}. On note Lin la famille des langages linéaires.
2. On considère le système de réécriture (type 0) Rn = (⌃n , Pn0 ) dont les règles
sont Pn0 = {(ai āi , ") | 1  i  n}. Exemples :
⇤
Montrer que Dn⇤ = {w 2 ⌃⇤n | w ! " dans Rn }. I Le langage {an bn | n 0} est linéaire.
⇤
3. Soit un alphabet disjoint de ⌃n , ⌃ = ⌃n [ et L ✓ ⌃ un langage. I Le langage {an bn cp | n, p 0} est linéaire.
⇤ ⇤
On définit la clôture clot(L) = {v 2 ⌃ | 9w 2 L, w ! v dans Rn }.
Montrer que si L est reconnaissable, alors clot(L) aussi. Proposition :
On définit la réduction red(L) = {v 2 clot(L) | v !
6 dans Rn }. Un langage est rationnel si et seulement si il peut être engendré par une grammaire
Montrer que si L est reconnaissable, alors red(L) aussi. linéaire gauche (ou droite).
89/197 90/197
Hiérarchie de Chomsky Bibliographie

[4] Jean-Michel Autebert.
Théorie des langages et des automates.
Masson, 1994.
Théorème : Chomsky [5] Jean-Michel Autebert, Jean Berstel et Luc Boasson.
1. Les langages réguliers (type 3) sont strictement contenus dans les langages Context-Free Languages and Pushdown Automata.
linéaires. Handbook of Formal Languages, Vol. 1, Springer, 1997.
2. Les langages linéaires sont strictement contenus dans les langages algébriques [7] Olivier Carton.
(type 2). Langages formels, calculabilité et complexité.
3. Les langages algébriques propres (type 2) sont strictement contenus dans les Vuibert, 2008.
langages contextuels (type 1). [9] John E. Hopcroft et Je↵rey D. Ullman.
4. les langages contextuels (type 1) sont strictement contenus dans les langages Introduction to automata theory, languages and computation.
récursifs. Addison-Wesley, 1979.
5. les langages récursifs sont strictement contenus dans les langages [10] Dexter C. Kozen.
récursivement énumérables (type 0). Automata and Computability.
Springer, 1997.
[14] Jacques Stern.
Fondements mathématiques de l’informatique.
Mc Graw Hill, 1990.
91/197 92/197
Plan Arbres de dérivation
Introduction
Définition :
Automates d’arbres Soit G = (⌃, V, P, S) une grammaire.
Grammaires Un arbre de dérivation pour G est un arbre t étiqueté dans V [ ⌃ [ {"} tel que
chaque nœud interne u est étiqueté par une variable x 2 V et si les fils de u portent
les étiquettes ↵1 , . . . , ↵k alors (x, ↵1 · · · ↵k ) 2 P .
5 Langages algébriques
Arbres de dérivation De plus, si k 6= 1, on peut supposer ↵1 , . . . , ↵k 6= ".
Propriétés de clôture
Exemple :
Formes normales et algorithmes
Arbres de dérivation pour les expressions.
Problèmes sur les langages algébriques Mise en évidence des priorités ou de l’associativité G ou D.
Forme normale de Greibach
Équations algébriques
Automates à pile
93/197 94/197
Analyse syntaxique
Arbres de dérivation Grammaires et automates d’arbres
Lemme : Dérivations et arbres de dérivation
Soit G = (⌃, V, P, S) une grammaire.
⇤
1. Si x ! ↵ une dérivation de G alors il existe un arbre de dérivation t de G tel
que rac(t) = x et Fr(t) = ↵.
⇤
2. Si t un arbre de dérivation de G alors il existe une dérivation rac(t) ! Fr(t) Théorème :
dans G. 1. Soit L un langage d’arbres reconnaissable.
⇤
Si Fr(t) 2 ⌃⇤ alors on peut faire une dérivation gauche rac(t) !g Fr(t). Le langage Fr(L) des frontières des arbres de L est algébrique.
Une dérivation est gauche si on dérive toujours le non terminal le plus à gauche. 2. Soit L0 un langage algébrique propre (" 2
/ L0 ).
Il existe un langage d’arbres reconnaissable L tel que L0 = Fr(L).
Remarques :
I 2 dérivations sont équivalentes si elles sont associées au même arbre de
dérivation.
I Il y a bijection entre dérivations gauches terminales et arbres de dérivation
ayant une frontière dans ⌃⇤ .
I Si la grammaire est linéaire, il y a bijection entre dérivations et arbres de
dérivations.
95/197 96/197
Ambiguı̈té Lemme d’itération
Définition : Ambiguı̈té
I Une grammaire est ambiguë s’il existe deux arbres de dérivations (distincts) de
même racine et de même frontière.
I Un langage algébrique est non ambigu s’il existe une grammaire non ambiguë Théorème : Bar-Hillel, Perles, Shamir ou Lemme d’itération
qui l’engendre. Soit L 2 Alg, il existe N 0 tel que pour tout w 2 L,
si |w| N alors on peut trouver une factorisation w = ↵u v avec
Exemples :
|uv| > 0 et |u v| < N et ↵un v n 2 L pour tout n 0.
I La grammaire S ! SS + aSb + " est ambiguë mais elle engendre un langage
non ambigu. Exemple :
I La grammaire E ! E + E | E ⇥ E | a | b | c est ambiguë et engendre un Le langage L1 = {an bn cn | n 0} n’est pas algébrique.
langage rationnel.
Proposition : Tout langage rationnel peut être engendré par une gram- Corollaire :
maire linéaire droite non ambiguë. Les familles Alg et Lin ne sont pas fermées par intersection ou complémentaire.
Exercice : if then else

Montrer que la grammaire suivante est ambiguë.
S ! if c then S else S | if c then S | a
Montrer que le langage engendré n’est pas ambigu.
97/197 98/197
Lemme d’Ogden Lemme d’Ogden
Plus fort que le théorème de Bar-Hillel, Perles, Shamir. Exercice :

Le langage L2 = {an bn cp dp | n, p 0} est algébrique mais pas linéaire.
Lemme : Ogden Corollaire :
Soit G = (⌃, V, P, S) une grammaire. Il existe un entier N 2 N tel que pour tout La famille Lin n’est pas fermée par concaténation ou itération.
x 2 V et w 2 Lb G (x) contenant au moins N lettres distinguées, il existe y 2 V et
↵, u, , v, 2 (⌃ [ V )⇤ tels que Exercice :
I w = ↵u v , Le langage L3 = {an bn cp | n, p > 0} [ {an bp cp | n, p > 0} est linéaire et
⇤ ⇤ ⇤
I x ! ↵y , y ! uyv, y ! , (inhéremment) ambigu.
I u v contient moins de N lettres distinguées,
I soit ↵, u, soit , v, contiennent des lettres distiguées.
Corollaire :
Les langages non ambigus ne sont pas fermés par union.
99/197 100/197
Propriétés de clôture Transductions rationnelles
Proposition :
1. La famille Alg est fermée par concaténation, itération. Définition : Transduction rationnelle
2. La famille Alg est fermée par substitution algébrique. Une transduction rationnelle (TR) ⌧ : A⇤ ! P(B ⇤ ) est la composée d’un morphisme
inverse, d’une intersection avec un rationnel et d’un morphisme.
3. Les familles Alg et Lin sont fermées par union et miroir.
4. Les familles Alg et Lin sont fermées par intersection avec un rationnel. ∩K
C∗ C∗
5. Les familles Alg et Lin sont fermées par morphisme.
6. Les familles Alg et Lin sont fermées par projection inverse. ϕ−1 ψ
7. Les familles Alg et Lin sont fermées par morphisme inverse. τ
A∗ B∗
Définition : Substitutions algébriques Soient A, B, C trois alphabets, K 2 Rat(C ⇤ ) et ' : C ⇤ ! A⇤ et : C ⇤ ! B ⇤ deux

Une substitution : A ! P(B ⇤ ) est algébrique si 8a 2 A, (a) 2 Alg morphismes. L’application ⌧ : A⇤ ! P(B ⇤ ) définie par ⌧ (w) = (' 1 (w) \ K) est
une TR.
Définition : Projection
Proposition :
La projection de A sur B ✓ A est le morphisme
( ⇡ : A⇤ ! B ⇤ défini par
Les familles Alg, Lin et Rat sont fermées par TR.
a si a 2 B
⇡(a) =
" sinon.
101/197 102/197
Transductions rationnelles Grammaires réduites

X
Théorème : Chomsky et Schützenberger La taille d’une grammaire G = (⌃, V, P, S) est |G| = |⌃| + |V | + 1 + |↵|.
x!↵2P
Les propositions suivantes sont équivalentes :
1. L est algébrique. Définition : Grammaires réduites
2. Il existe une TR ⌧ telle que L = ⌧ (D2⇤ ). La grammaire G = (⌃, V, P, S) est réduite si toute variable x 2 V est
⇤
3. Il existe un entier n, un rationnel K et un morphisme alphabétique tels que I productive : LG (x) 6= ;, i.e., 9 x ! u 2 ⌃⇤ , et
L = (Dn⇤ \ K). ⇤
I accessible : il existe une dérivation S ! ↵x avec ↵, 2 (⌃ [ V )⇤ .
Corollaire :
Lemme : Soit G = (⌃, V, P, S) une grammaire.
Les langages non ambigus ne sont pas fermés par morphisme.
1. On peut calculer l’ensemble des variables productives de G O(|G|).
Théorème : Elgot et Mezei, 1965 2. On peut décider si LG (S) = ; O(|G|).
La composée de deux TR est encore une TR. 3. On peut calculer l’ensemble des variables accessibles de G O(|G|).
Théorème : Nivat, 1968 Corollaire : Soit G = (⌃, V, P, S) une grammaire

Une application ⌧ : A⇤ ! P(B ⇤ ) est une TR si et seulement si son graphe
Si LG (S) 6= ;, on peut construire une grammaire réduite équivalente O(|G|).
{(u, v) | v 2 ⌧ (u)}
est une relation rationnelle (i.e., un langage rationnel de A⇤ ⇥ B ⇤ ). Preuve : Restreindre aux variables productives, puis aux variables accessibles.
103/197 104/197
Grammaires propres Grammaires quadratiques
Définition : Grammaires propres
La grammaire G = (⌃, V, P, S) est propre si P ✓ V ⇥ ((⌃ [ V )+ \ V ),
i.e., elle ne contient pas de règle de la forme x ! " ou x ! y avec x, y 2 V . Définition : Forme normale de Chomsky
Un langage L ✓ ⌃⇤ est propre si " 2 / L. Une grammaire G = (⌃, V, P, S) est en forme normale
1. quadratique si P ✓ V ⇥ (V [ ⌃)2
Lemme :
2. de Chomsky si P ✓ {(S, ")} [ (V ⇥ (V 2 [ ⌃)) et si (S, ") 2 P alors S
Soit G = (⌃, V, P, S) une grammaire. n’apparaı̂t dans aucun membre droit.
On peut calculer l’ensemble des variables x telles que " 2 LG (x) O(|G|).
On peut construire une grammaire équivalente sans "-règle autre que S ! " et dans Proposition :
ce cas S n’apparaı̂t dans aucun membre droit O(|G|).
On peut construire une grammaire équivalente en FN quadratique O(|G|).
Proposition :
On peut construire une grammaire équivalente en FN de Chomsky O(|G|2 ).
On peut construire une grammaire propre G0 qui engendre LG (S) \ {"} O(|G|2 ). Remarques :
Remarque : la réduction d’une grammaire propre est une grammaire propre. 1. La réduction d’une grammaire en FNC est encore en FNC.
Corollaire :
On peut décider si un mot u 2 ⌃⇤ est engendré par une grammaire G.
105/197 106/197
Problèmes décidables Problèmes indécidables

Proposition :
Proposition : Problème du mot : Cocke, Younger, Kasami [9, p. 139] Soient L, L0 deux langages algébriques et R un langage rationnel.
Soit G une grammaire algébrique. Les problèmes suivants sont indécidables :
On peut décider si un mot w est engendré par G en temps O(|w|3 ). I L \ L0 = ; ?
I L = ⌃⇤ ?
Exercice : I L = L0 ?
Soit G une grammaire algébrique et A un automate fini. I L ✓ L0 ?
Montrer que l’on peut décider en temps polynomial si L(G) \ L(A) 6= ;. I R✓L?
I L est-il rationnel ?
Proposition : Vide et finitude I L est-il déterministe ?
Soit G une grammaire algébrique. I L est-il ambigu ?
On peut décider si le langage engendré par G est vide, fini ou infini (PTIME). I L est-il algébrique ?
I L \ L0 est-il algébrique ?
107/197 108/197
Forme normale de Greibach Forme normale de Greibach
Preuve
Définition :
Soit G = (⌃, V, P ) une grammaire⇢ avec V = {x1 , . . . , xn }.
La grammaire G = (⌃, V, P ) est en ↵i,j = xi 1 P (xj ) ✓ (⌃ [ V )⇤
FNG (forme normale de Greibach) si P ✓ V ⇥ ⌃V ⇤ Pour i, j 2 {1, . . . , n} on pose
j = PP (xj ) \ (⌃ · (⌃ [ V )⇤ [ {"})
FNPG (presque Greibach) si P ✓ V ⇥ ⌃(V [ ⌃)⇤ de sorte que les règles de G s’écrivent xj ! i xi ↵i,j + j pour 1  j  n.
FNGQ (Greibach quadratique) si P ✓ V ⇥ (⌃ [ ⌃V [ ⌃V 2 )
On peut écrire P vectoriellement : X ! XA + B
avec X = (x1 , . . . , xn ), B = ( 1 , . . . , n ) et A = (↵i,j )1i,jn .
Remarque : on passe trivialement d’une FNPG(Q) à une FNG(Q).
On définit G0 = (⌃, V 0 , P 0 ) par V 0 = V ] {yi,j | 1  i, j  n} et
Théorème : P
X ! BY + B xj ! Pk k yk,j + j
P0 : i.e.
Soit G = (⌃, V, P ) une grammaire propre. Y ! AY + A yi,j ! k ↵i,k yk,j + ↵i,j
On peut construire G0 = (⌃, V 0 , P 0 ) en FNG équivalente à G,
i.e., V ✓ V 0 et LG (x) = LG0 (x) pour tout x 2 V . avec Y = (yi,j )1i,jn .
La difficulté est d’éliminer la récursivité gauche des règles.

Proposition : Equivalence des grammaires
Les grammaires G et G0 sont équivalentes, i.e., 8x 2 V , LG (x) = LG0 (x).
109/197 110/197
Forme normale de Greibach Équations algébriques

Remarque : Grammaire propre
Si G est propre alors pour 1  i, j  n on a Définition : Système d’équations algébriques
↵i,j ✓ (⌃ [ V )+ et j ✓ ⌃ · (⌃ [ V )
⇤ Un système d’équations algébriques est un triplet (⌃, V, P ) où :
donc les règles X ! BY + B de G0 sont en FNPG. I ⌃ est l’alphabet terminal,
I V = {X1 , . . . , Xn } est un ensemble fini de variables disjoint de ⌃,
On définit G00 à partirPde G0 en remplaçant chaque variable x` en tête d’un mot de I P = (P1 , . . . , Pn ) avec Pi ✓ (⌃ [ V )⇤ (non nécessairement fini).
↵i,j par sa définition k k yk,` + ` . 8
< X1 = P1 (X)
>
Proposition : FNG et FNGQ On écrit le système d’équations X = P (X) ou ..
> .
:
I Les grammaires G et G00 sont équivalentes. Xn = Pn (X)
I Si G est une grammaire propre alors G00 est en FNPG. Une solution est un tuple L = (L1 , . . . , Ln ) de langages sur ⌃ vérifiant L = P (L).
I Si G est propre et en FN de Chomsky, alors G00 est en FNGQ.
Exemple :
⇢
Exemples : Mettre les grammaires suivantes en FNG(Q) L = (a+ b+ , ab⇤ ) est solution de
X1 = aX1 + X2 b
⇢ ⇢ X2 = X2 b + a
x1 ! x1 b + a x1 ! x1 (x1 + x2 ) + (x2 a + b)
G1 : G2 :
x2 ! x1 b + ax2 x2 ! x1 x2 + x2 x1 + a
111/197 112/197
Équations algébriques Équations algébriques
Définition :
Théorème : Existence de solutions Un système d’équations (⌃, V, P ) est
Tout système (⌃, V, P ) d’équations algébriques admet une plus petite solution : I propre si P \ (V [ {"}) = ; pour tout i
i
G n I strict si Pi ✓ {"} [ (⌃ [ V )⇤ ⌃(⌃ [ V )⇤ pour tout i
L= L
n 0 Le système est faiblement propre (resp. strict) s’il existe k > 0 tel que X = P k (X)
est propre (resp. strict).
0 n+1 n
avec L = (;, . . . , ;) et L = P (L ).
Théorème : Unicité
Exercice : Grammaire et équations algébriques Tout système (⌃, V, P ) d’équations algébriques faiblement strict ou faiblement pro-
Soit G = (⌃, V, Q) une grammaire avec V = {X1 , . . . , Xn }. pre admet une solution unique.
Le système d’équations associé est (⌃, V, P ) où Pi = {↵ 2 (⌃[V )⇤ | (Xi , ↵) 2 Q}.
Exemple :
Montrer que (LG (X1 ), . . . , LG (Xn )) est la plus petite solution du système
D1⇤ est l’unique solution de X = aXbX + ".
d’équations X = P (X).
L est l’unique solution de X = aXX + b.
On en déduit L = D1⇤ b.
113/197 114/197
Équations algébriques Plan

Introduction
Théorème : Résolution par élimination
⇢
On considère le système
X = P (X, Y ) Langages reconnaissables
Y = Q(X, Y )
avec X = (X1 , . . . , Xn ) et Y = (Y1 , . . . , Ym ). Automates d’arbres
Soit K une solution de Y = Q(X, Y ) sur ⌃ [ {X1 , . . . , Xn }.
Soit L une solution de X = P (X, K) sur ⌃. Grammaires
⇢
X = P (X, Y )
Alors, (L, K(L)) est une solution du système Langages algébriques
Y = Q(X, Y )
Exemple : 6 Automates à pile

⇢
X1 = aX1 + bX2 + " Définition et exemples
Résolution par élimination du système
X2 = bX1 + aX2 Modes de reconnaissance
Lien avec les langages algébriques
Exemple : Mots de pile
⇢
X =YX +b Langages déterministes
Résolution par élimination du système
Y = aX Complémentaire
115/197 116/197
Analyse syntaxique
Automates à pile Automates à pile
Définition : A = (Q, ⌃, Z, T, q0 z0 , F ) où Exemples :
I Q ensemble fini d’états I L1 = {an bn cp | n, p > 0} et L2 = {an bp cp | n, p > 0}
I ⌃ alphabet d’entrée I L = L1 [ L2 (non déterministe)
I Z alphabet de pile
I T ✓ QZ ⇥ (⌃ [ {"}) ⇥ QZ ⇤ ensemble fini de transitions Exercices :
I q0 z0 2 QZ configuration initiale 1. Montrer que le langage {ww̃ | w 2 ⌃⇤ } et son complémentaire peuvent être
acceptés par un automate à pile.
I F ✓ Q acceptation par état final.
2. Montrer que le complémentaire du langage {ww | w 2 ⌃⇤ } peut être accepté
De plus, A est temps-réel s’il n’a pas d’"-transition. par un automate à pile.
Définition : Système de transitions (infini) associé 3. Soit A = (Q, ⌃, Z, T, q0 z0 , F ) un automate à pile. Montrer qu’on peut
construire un automate à pile équivalent A0 tel que
I T = (QZ ⇤ , T 0 , q0 z0 , F Z ⇤ ) T 0 ✓ Q0 Z ⇥ (⌃ [ {"}) ⇥ Q0 Z 2 .
I Une configuration de A est un état ph 2 QZ ⇤ de T 4. Soit A un automate à pile. Montrer qu’on peut construire un automate à pile
a
I Transitions de T : T 0 = {pzh ! qgh | (pz, a, qg) 2 T }. équivalent A0 tel que les mouvements de la pile sont uniquement du type push
I
w
L(A) = {w 2 ⌃⇤ | 9 q0 z0 ! qh 2 F Z ⇤ dans T }. ou pop.
117/197 118/197
Propriétés fondamentales Acceptation généralisée

Définition :
Soit A = (Q, ⌃, Z, T, q0 z0 ) un automate à pile et K ✓ QZ ⇤ un langage reconnaiss-
Lemme : fondamental able. Le langage reconnu par A avec acceptation généralisée K est
w
LK (A) = {w 2 ⌃⇤ | 9 q0 z0 ! qh 2 K dans T }
Soit A = (Q, ⌃, Z, T, q0 z0 ) un automate à pile.
Cas particuliers :
1. Si pg w! p0 g 0 est un calcul de A et h 2 Z ⇤ alors
n
w
pgh n! p0 g 0 h est aussi un calcul de A.
I K = F Z ⇤ : acceptation classique par état final.
I K = Q : acceptation par pile vide.
1 a n a
2. Si p0 g0 ! p1 g 1 · · · ! pn gn est un calcul de A tel que |gi | > k pour I K = F : acceptation par pile vide et état final.
0  i < n alors il existe h 2 Z k tel que gi = gi0 h pour 0  i  n et I K = QZ 0 Z ⇤ avec Z 0 ✓ Z : acceptation par sommet de pile.
a1 an
p0 g00 ! p1 g10 · · · ! pn gn0 est un calcul de A.
Exemple :
3. pgh w
! r est un calcul de A ssi il existe deux calculs de A :
n
w1
pg n!
w2
q et qh n! r avec w = w1 w2 et n = n1 + n2 . L = {an bn | n 0} peut être accepté par pile vide ou par sommet de pile.
1 2
Proposition : Acceptation généralisée

Soit A un automate à pile avec acceptation généralisée K, on peut e↵ectivement
construire un automate à pile A0 acceptant par état final tel que LK (A) = L(A0 ).
119/197 120/197
Acceptation généralisée Automates à pile et grammaires
Preuve : Acceptation généralisée
Soit A = (Q, ⌃, Z, T, q0 z0 ) un automate à pile et K ✓ QZ ⇤ un langage reconnu
par l’automate fini déterministe B = (P, Z [ Q, , p0 , F ) avec P \ Q = ;. Proposition :
Soit A0 = (Q0 , ⌃, Z ] {?}, T 0 , q00 ?, {f }) avec Q0 = Q ] P ] {q00 , f }, et
"
Soit A = (Q, ⌃, Z, T, q0 z0 ) un automate à pile reconnaissant par pile vide. On peut
1. q00 · ? ! q0 · z0 ? 2 T 0 , Initialisation construire une grammaire G qui engendre L(A).
2. T ✓ T 0 , Simulation De plus, si A est temps-réel alors G est en FNG.
" 0
3. q · z ! (p0 , q) · z 2 T , si q 2 Q et z 2 Z ] {?}, Acceptation
"
4. p · z ! (p, z) · " 2 T 0 , si p 2 P et z 2 Z, Acceptation Proposition :
" 0 Soit G = (⌃, V, P, S) une grammaire. On peut construire un automate à pile simple
5. p · ? ! f · " 2 T , si p 2 F , Acceptation
(un seul état) A qui accepte LG (S) par pile vide.
On a L(A, K) = L(A0 ).
De plus, si G est en FNPG alors on peut construire un tel A temps-réel.
Remarque: A0 reconnaı̂t aussi L(A, K) par pile vide.
Si G est en FNGQ alors on peut construire un tel A standardisé (T ✓ Z ⇥⌃⇥Z 2 ).
exo: Modifier A0 pour qu’il reconnaisse L(A, K) par sommet de pile.
Corollaire :
Tous les modes d’acceptation ci-dessus sont équivalents.
121/197 122/197
Accessibilité et mots de pile Accessibilité et mots de pile (Preuve)

On définit = Q ] Z ] Q ] Z et la réduction sur ⇤ par
⇢ red
Proposition : Accessibilité et mots de pile qq ! " pour q 2 Q
red
zz ! " pour z 2 Z
Soit A = (Q, ⌃, Z, T, q0 z0 ) un automate à pile. red
⇤ ⇤
Pour pg 2 QZ ⇤ , on note Pour L ✓ on pose Clot(L) = {w 2 | 9v 2 L, v ⇤! w}.
C(pg) = {qh 2 QZ ⇤ | 9 pg !
+ qh dans T }
Lemme : Clôture
Si L ✓ ⇤ est un langage rationnel alors Clot(L) ✓ ⇤ aussi.
l’ensemble des configurations accessibles à partir de pg. De plus, on peut e↵ectivement construire un automate pour Clot(L) à partir d’un
On peut e↵ectivement construire un automate fini B qui reconnaı̂t C(pg). automate pour L.
a +
Corollaire : Décidabilité Soit K = {qhxp | 9 px ! qh 2 T } ✓ , langage fini donc rationnel.
Soit A = (Q, ⌃, Z, T, q0 z0 , F ) un automate à pile. Lemme :
On peut décider si L(A) = ;.
Soit n 0,
n red
il existe un calcul pg !
n qh dans T ssi il existe w 2 K tel que wpg 2n! qh
Corollaire : C(pg) = Clot(K + · pg) \ QZ ⇤ .

123/197 124/197
Calculs d’accessibilité Langages déterministes
Corollaire : Définition : Automate à pile déterministe
Soit A = (Q, ⌃, Z, T, q0 z0 ) un automate à pile. A = (Q, ⌃, Z, T, q0 z0 , F ) est déterministe si
On peut e↵ectivement calculer les ensembles suivants : I 8(pz, a) 2 QZ ⇥ (⌃ [ {"}), |T (pz, a)|  1,
1. X = {(p, x, q) 2 Q ⇥ Z ⇥ Q | 9 px !
+ q dans T }
I 8 pz 2 QZ, T (pz, ") 6= ; =) 8 a 2 ⌃, T (pz, a) = ;
2. Y = {(p, x, q, y) 2 Q ⇥ Z ⇥ Q ⇥ Z | 9 px !
+ qyh dans T } Un langage L ✓ ⌃⇤ est déterministe s’il existe un automate à pile déterministe qui
3. W = {(p, x, q, y) 2 Q ⇥ Z ⇥ Q ⇥ Z | 9 px ! accepte L par état final.
+ qy dans T }
"
4. X 0 = {(p, x, q) 2 Q ⇥ Z ⇥ Q | 9 px !
+ q dans T } Exemples :
"
5. Y 0 = {(p, x, q, y) 2 Q ⇥ Z ⇥ Q ⇥ Z | 9 px !
+ qyh dans T }
"
1. {an ban | n 0} peut être accepté par un automate D+TR mais pas par un
6. W 0 = {(p, x, q, y) 2 Q ⇥ Z ⇥ Q ⇥ Z | 9 px !
+ qy dans T } automate D+S car il n’est pas fermé par préfixe.
2. Le langage {an bp can | n, p > 0} [ {an bp dbp | n, p > 0} est déterministe mais
Exercice : pas D+TR.
Montrer qu’on peut e↵ectivement calculer les ensembles suivants : Exercices :
1. V = {(p, x) 2 Q ⇥ Z | 9 px !
! dans T } 1. Montrer que Dn⇤ est D+TR mais pas D+S.
0 "
2. V = {(p, x) 2 Q ⇥ Z | 9 px !
! dans T } 2. Montrer que le langage {an bn | n > 0} [ {an b2n | n > 0} est non ambigu
mais pas déterministe.
125/197 126/197
Acceptation par pile vide Lemme d’itération pour les déterministes
Exemples :
1. Le langage {an ban | n 0} peut être accepté par pile vide par un automate
D+TR+S. Lemme : Itération
n p n n p p
2. Le langage {a b ca | n, p > 0} [ {a b db | n, p > 0} peut être accepté par Soit L ✓ ⌃⇤ un langage déterministe. Il existe un entier N 2 N tel que tout mot
pile vide par un automate D. w 2 L contenant au moins N lettres distinguées se factorise en w = ↵u v avec
1. 8p 0 : w = ↵up v p 2 L(A),
Exercices : 2. u v contient moins de N lettres distinguées,
1. Montrer qu’un langage L est déterministe et préfixe (L \ L⌃+ = ;) ssi il 3. soit ↵, u, soit , v, contiennent des lettres distiguées,
existe un automate déterministe qui accepte L par pile vide. 0 ⇤
4. pour tout 2⌃ ,
2. Montrer que pour les automates à pile déterministes, l’acceptation par pile
0 0
vide est équivalente à l’acceptation par pile vide ET état final. 9p : ↵up v p 2L =) 8p : ↵up v p 2L
Exercice :
Montrer que Dn⇤ peut être accepté par sommet de pile par un automate D+TR+S.
127/197 128/197
Langages déterministes Complémentaire
Proposition : Décidabilité et indécidabilité
On ne peut pas décider si un langage algébrique est déterministe.
Soient L, L0 deux langages déterministes et R un langage rationnel.
Théorème : Les déterministes sont fermés par complémentaire.
Soit A = (Q, ⌃, Z, T, q0 z0 , F ) un automate à pile déterministe, on peut e↵ective-
Les problèmes suivants sont décidables : ment construire un automate à pile déterministe A0 qui reconnaı̂t ⌃⇤ \ L(A).
I L=R?
I R✓L?
Il y a deux difficultés principales :
I L est-il rationnel ?
1. Un automate déterministe peut se bloquer (deadlock) ou entrer dans un
I L = L0 ?
"-calcul infini (livelock). Dans ce cas il y a des mots qui n’admettent aucun
Les problèmes suivants sont indécidables : calcul dans l’automate.
I L \ L0 = ; ? 2. Même avec un automate déterministe, un mot peut avoir plusieurs calculs
I L ✓ L0 ? ("-transitions à la fin) certains réussis et d’autres non.
I L \ L0 est-il algébrique ?
I L \ L0 est-il déterministe ?
I L [ L0 est-il déterministe ?
129/197 130/197
Blocage Blocage
Proposition : Suppression des blocages
Définition : Blocage
Soit A = (Q, ⌃, Z, T, q0 z0 , F ) un automate à pile déterministe, on peut ef-
Un automate à pile A = (Q, ⌃, Z, T, q0 z0 ) est sans blocage si pour toute configu-
" a fectivement construire un automate à pile déterministe sans blocage A0 =
ration accessible p↵ et pour toute lettre a 2 ⌃ il existe un calcul p↵ !
⇤ !. (Q0 , ⌃, Z 0 , T 0 , q00 z00 , F 0 ) qui reconnaı̂t le même langage.
Proposition : Critère d’absence de blocage Preuve
Un automate déterministe est sans blocage si et seulement si pour toute configura- Q0 = Q ] {q00 , d, f }, F 0 = F ] {f }, Z 0 = Z ] {?}, z00 = ? et
tion accessible p↵ on a pour p 2 Q, a 2 ⌃ et x 2 Z
1. ↵ 6= ", et donc on peut écrire ↵ = x avec x 2 Z, "
1. q00 ? ! q0 z0 ?,
" a
2. px ! ou 8a 2 ⌃, px !, a a
"
2. Si px ! q↵ 2 T alors px ! q↵ 2 T 0 ,
3. px 6 !
! . a " a
3. Si px 6 ! et px 6! dans A alors px ! dx 2 T 0 ,
De plus, ce critère est décidable. " " 0 "
4. Si px 6 !
! dans A et px ! q↵ 2 T alors px ! q↵ 2 T ,
" " 0 "
Remarque : 5. Si px !
! dans A et 9 px !
⇤ q↵ avec q 2 F alors px ! f x 2 T ,
" " "
Si A est sans blocage alors chaque mot w 2 ⌃⇤ a un unique calcul maximal (et fini) 6. Si px !
! dans A et 8 px !
⇤ / F alors px ! dx 2 T 0 ,
q↵ on a q 2
" " a a a
q0 z0 w⇤! p↵ 6! dans A (avec ↵ 6= "). 7. p? ! d?, d? ! d?, dx ! dx et f x ! dx.
Cette construction est e↵ective.
131/197 132/197
Complémentaire Langages déterministes
Proposition :
Exercice :
Soit A = (Q, ⌃, Z, T, q0 z0 , K) un automate à pile déterministe avec acceptation
ment construire un automate à pile déterministe A0 qui reconnaı̂t ⌃⇤ \ L(A).
généralisée par le langage rationnel K ✓ QZ ⇤ .
Montrer qu’on peut e↵ectivement construire un automate à pile déterministe
Proposition : équivalent reconnaissant par état final.
ment construire un automate à pile déterministe équivalent A0 tel qu’on ne puisse Exercice :
pas faire d’"-transition à partir d’un état final de A0 . Soit A un automate à pile déterministe. Montrer qu’on peut e↵ectivement con-
struire un automate à pile déterministe qui reconnaı̂t le même langage et dont les
Exercice : "
"-transitions sont uniquement e↵açantes : px ! q.
Montrer que tout langage déterministe est non ambigu.
133/197 134/197
Plan Bibliographie
Introduction
Automates d’arbres [1] Alfred V. Aho, Ravi Sethi et Je↵rey D. Ullman.

Compilers: principles, techniques and tools.
Addison-Wesley, 1986.
Grammaires
[2] Alfred V. Aho et Je↵rey D. Ullman.
The theory of parsing, translation, and compiling. Volume I: Parsing.
Langages algébriques
Prentice-Hall, 1972.
[9] John E. Hopcroft et Je↵rey D. Ullman.
Automates à pile Introduction to automata theory, languages and computation.
Addison-Wesley, 1979.
7 Analyse syntaxique
Analyse descendante (LL)
Analyse ascendante (LR)
Analyseur SLR
Analyseur LR(1)
135/197 136/197
Analyse syntaxique Analyse syntaxique
Buts :
I Savoir si un programme est syntaxiquement correct.
Rappels : le problème du mot est décidable
I Construire l’arbre de dérivation pour piloter la génération du code.
I Programmation dynamique : O(|w|3 ).
Ce n’est pas assez efficace.
Rappels : I en lisant le mot si on a un automate à pile déterministe complet.
⇤
O(|w|) si l’automate est temps réel ou si les "-transitions ne font que dépiler.
I Un programme est un mot w 2 ⌃ (⌃ est l’alphabet ASCII). Mais la grammaire qui définit la syntaxe du langage de programmation peut
L’ensemble des programmes syntaxiquement corrects forme un langage être non déterministe ou ambiguë.
L ✓ ⌃⇤ .
Ce langage est algébrique : la syntaxe du langage de programmation est Exercice :
définie par une grammaire G = (⌃, V, P, S).
+
I Pour tester si un programme w est syntaxiquement correct, il faut résoudre le Si la grammaire n’est pas récursive à gauche (x ! 6 x↵), on peut construire un
problème du mot : est-ce que w 2 LG (S) ? analyseur récursif avec backtracking. (Cet analyseur n’est pas efficace.)
I L’arbre de dérivation est donné par la suite des règles utilisées lors d’une
dérivation gauche (ou droite).
137/197 138/197
Analyse descendante (LL) Analyse descendante (LL)

Définition : Automate LL ou expansion/vérification Problème :
Soit G = (⌃, V, P, S) une grammaire réduite. L’automate ainsi obtenu est en général non déterministe.
On construit l’automate à pile simple non déterministe qui accepte par pile vide :
A = (⌃, ⌃ [ V, T, S) où les transitions de T sont des Solution :
I expansions : {(x, ", ↵) | (x, ↵) 2 P } ou Pour lever le non déterminisme de l’automate on s’autorise à regarder les k
I vérifications : {(a, a, ") | a 2 ⌃}. prochaines lettres du mot.
Remarque : sommet de pile à gauche.
Exemple :
Lemme : 1. G1 : S ! aSb + ab.
⇤ ⇤ On peut lever le non déterminisme de l’automate associé à la grammaire G1
Soient x, y 2 V , w 2 ⌃ et ↵ 2 (⌃ [ V ) .
⇤ w
en regardant les 2 prochaines lettres.
1. 9 ↵ ! w dérivation dans G ssi 9 ↵ ! " calcul dans A.
⇤ w 8
2. 9 ↵ ! wy dérivation gauche dans G ssi 9 ↵ ! y calcul dans A. < E ! E+T |T
2. G2 : T ! T ⇥F |F
Définition : :
F ! (E) | a | b | c
⇢ On ne peut pas lever le non déterminisme de l’automate associé à la
L : le mot est lu de gauche à droite dans A.
Analyse LL : grammaire G2 en regardant les k prochaines lettres.
L : on construit une dérivation gauche dans G.
139/197 140/197
Analyse LL avec lookahead Analyse LL avec lookahead
Définition : Table d’analyse LL avec lookahead
Exemple :
Une k-table d’analyse pour G est une application M : V ⇥ ⌃k ! 2P telle que
pour x 2 V et v 2 ⌃k on a M (x, v) ✓ P \ ({x} ⇥ (⌃ [ V )⇤ ). 1. Construire une 2-table d’analyse déterministe et complète pour G1 .
La table est déterministe si |M (x, v)|  1 pour tout x 2 V et v 2 ⌃k . 2. Construire une 1-table d’analyse déterministe et complète pour la grammaire
usuelle du langage de Dyck Dn⇤ sur n paires de parenthèses:
Définition : Analyseur LL avec lookahead
S ! " | a1 Sb1 S | · · · | an Sbn S
Soit G = (⌃, V, P, S) une grammaire et soit M une k-table d’analyse pour G.
L’analyseur LL défini par M , noté AM , est l’automate LL A associé à G dont les
Exercice :
expansions sont pilotées par M :
Si x 2 V est au sommet de pile et si v 2 ⌃k est le mot formé des (au plus) k Transformer l’analyseur LL défini par une table déterministe en un automate à pile
prochaines lettres à lire, alors AM choisit une expansion dans M (x, v). déterministe classique (sans lookahead) équivalent.
L’analyseur est bloqué (erreur) si M (x, v) = ;.
Objectif de l’analyse LL(k)
Corollaire : L(AM ) ✓ L(A) = LG (S) Étant donnés une grammaire G et un entier k, construire automatiquement une
k-table d’analyse déterministe et complète pour la grammaire G.
Définition : L’analyseur AM est complet si L(AM ) = L(A) = LG (S)
On dit aussi que la table M est complète pour G.
141/197 142/197
Analyse descendante Firstk Calcul de Firstk

Définition : First Définition : Algorithme de calcul pour Firstk (k > 0)
(
w si |w|  k On définit Xm (↵) pour ↵ 2 ⌃ [ V et m 0 par :
I Pour w 2 ⌃⇤ et k 0, on définit Firstk (w) =
w[k] sinon. I si a 2 ⌃ alors Xm (a) = {a} pour tout m 0,
I ⇤
Pour L ✓ ⌃ et k 0, Firstk (L) = {Firstk (w) | w 2 L}. I si x 2 V alors X0 (x) = ; et
I Soit G = (⌃, V, P, S) une grammaire algébrique, ↵ 2 (⌃ [ V )⇤ et k 0, [
Xm+1 (x) = Firstk (Xm (↵1 ) · · · Xm (↵n ))
Firstk (↵) = Firstk (LG (↵)) ✓ ⌃k x!↵1 ···↵n 2P
Remarque : Proposition : Point fixe (k > 0)

1. Xm (↵) ✓ Xm+1 (↵)
Firstk (↵ ) = Firstk (Firstk (↵) · Firstk ( ))
2. Xm (↵) ✓ Firstk (↵)
m
Exemple : 3. Si ↵ ! w 2 ⌃⇤ alors Firstk (w) 2 Xm (↵).
S
Calculer First2 (E) pour la grammaire G2 . 4. Firstk (↵) = m 0 Xm (↵)
Ceci fournit un algorithme pour calculer Firstk (↵) pour ↵ 2 ⌃ [ V .
Remarque : Pour 2 (⌃ [ V )⇤ on utilise Firstk (↵ ) = Firstk (Firstk (↵) · Firstk ( )).
Pour ↵ 2 (⌃ [ V )⇤ , First0 (↵) = {"} ssi toutes les variables de ↵ sont productives. En particulier, Firstk (") = {"}.
143/197 144/197
Analyse descendante LL(k) Analyse descendante LL(k)
Définition : LL(k)
⇤
Une grammaire G = (⌃, V, P, S) est LL(k) si pour toute dérivation S ! x avec
x 2 V et pour toutes règles x ! ↵ et x ! avec ↵ 6= , on a Exercices :
1. Construire une k-table d’analyse déterministe et complète pour une
Firstk (↵ ) \ Firstk ( ) = ;. grammaire LL(k).
Remarque : on peut se restreindre aux dérivations gauches avec 2 ⌃⇤ , i.e., aux 2. Montrer qu’un langage LL(k) est déterministe.
calculs de l’automate LL. 3. Montrer que si l’automate expansion/vérification associé à une grammaire est
déterministe, alors la grammaire est LL(0).
Exemple : 4. Montrer qu’une grammaire LL(0) engendre au plus un mot.
1. La grammaire G1 est LL(2) mais pas LL(1). 5. Montrer que si G est en FNPG et que pour toutes règles x ! a↵ et x ! b
2. La grammaire G2 n’est pas LL(k). avec a, b 2 ⌃ on a a 6= b ou ↵ = , alors G est LL(1).
3. On peut transformer la grammaire G2 en une grammaire LL(1) équivalente. 6. Montrer que la réciproque est fausse.
Il suffit de supprimer la récursivité gauche. 7. Montrer qu’un langage rationnel admet une grammaire LL(1).
8
< E ! T E0 E 0 ! +T E 0 | "
0 0
G2 = T ! FT T 0 ! ⇥F T 0 | "
:
F ! (E) | a | b | c
145/197 146/197
Analyse descendante LL(k) Follow

Définition : Follow
Soit G = (⌃, V, P, S) une grammaire algébrique, x 2 V et k 0,
[ ⇤
Followk (x) = Firstk ( ) = {w 2 ⌃⇤ | 9 S ! x avec w 2 Firstk ( )}
Remarques : ⇤
| 9S ! x
I Étant donnés une grammaire G et un entier k, on peut décider si G est LL(k).
I Étant données deux grammaires LL(k), on peut décider si elles engendrent le Remarque : on peut se restreindre aux dérivations gauches avec 2 ⌃⇤ .
même langage.
I La hiérarchie des langages LL(k) est stricte.
Théorème : Caractérisation
Les ensembles (Followk (x))x2V satisfont le système d’équations :
I Étant donnée une grammaire G, on ne peut pas décider s’il existe un entier k
tel que G soit LL(k). [
Followk (S) = {"} [ Firstk ( Followk (y))
I Étant donnée une grammaire G, on ne peut pas décider s’il existe une y!↵S
grammaire équivalente qui soit LL(1). [
(x 6= S) Followk (x) = Firstk ( Followk (y))
y!↵x
Exemple :
Calculer Follow1 (x) pour chaque variable x de la grammaire G02 .
147/197 148/197
Calcul de Followk Fortement LL
Définition : Fortement LL(k)
Une grammaire G = (⌃, V, P, S) est fortement LL(k) si pour toutes règles x ! ↵
Définition : Algorithme de calcul pour Followk et x ! avec ↵ 6= , on a
Pour m 0 et x 2 V , on définit Ym (x) par :
Firstk (↵Followk (x)) \ Firstk ( Followk (x)) = ;
I Y0 (S) = {"} et Y0 (x) = ; si x 6= S
[
I Ym+1 (x) = Ym (x) [ Firstk ( Ym (y)) Proposition :
y!↵x 2P
Si une grammaire G est fortement LL(k) alors elle est LL(k).
Proposition : Point fixe Exemple :
1. Ym (x) ✓ Ym+1 (x)
1. La grammaire G1 est fortement LL(2).
2. Ym (x) ✓ Followk (x)
2. La grammaire G02 est fortement LL(1).
m
3. Si S ! x alors Firstk ( ) ✓ Ym (x). ⇢
S S ! axaa | bxba
3. La grammaire G3 =
4. Followk (x) = m 0 Ym (x) x ! b|"
Ceci fournit donc un algorithme pour calculer Followk (↵). est LL(2) mais pas fortement LL(2).
Proposition :
Une grammaire est LL(1) si et seulement si elle est fortement LL(1).
149/197 150/197
Analyseur fortement LL Analyse ascendante (LR)

Définition : Analyseur fortement LL(k) Définition : Automate shift/reduce (LR)
Soit G = (⌃, V, P, S) une grammaire. Soit G = (⌃, V, P, S) une grammaire.
La table d’analyse fortement LL(k) de G est définie pour x 2 V et v 2 ⌃k par On construit un automate à pile généralisé simple (non déterministe) B.
"
Alphabet de pile : ⌃ [ V . Initialement la pile est vide.
Mk (x, v) = {x ! ↵ | (x, ↵) 2 P et v 2 Firstk (↵Followk (x))} Transitions généralisées : T ✓ (⌃ [ V )⇤ ⇥ (⌃ [ {"}) ⇥ (⌃ [ V ) fini
L’analyseur fortement LL(k) associé est AMk .
I décalages (shift) : {(", a, a) | a 2 ⌃} ou
I réductions (reduce) : {(↵, ", x) | (x, ↵) 2 P }.
Proposition : Correction L’automate accepte lorsque la pile contient uniquement le symbole S.
Soit G = (⌃, V, P, S) une grammaire. Remarque : sommet de pile à droite.
La table d’analyse fortement LL(k) de G est complète: L(AMk ) = LG (S).
Si G est fortement LL(k) alors sa table d’analyse fortement LL(k) est déterministe. Exemples :
1. G1 : S ! aSb | ab
Exemple : 2. G2 : E ! E + T | T , T ! T ⇤ F | F , F ! (E) | id
1. Construire la table d’analyse fortement LL(2) de la grammaire G1 .
2. Construire la table d’analyse fortement LL(1) de la grammaire G02 . Définition :
⇢
3. Construire la table d’analyse fortement LL(1) de la grammaire usuelle du L : le mot est lu de gauche à droite.
Analyse LR :
langage de Dyck Dn⇤ . R : on construit une dérivation droite.
151/197 152/197
Analyse ascendante (LR) Conflits dans un automate LR
Exemple : Automate LR pour la grammaire G2 :
" ⇤
1 id ! F 7 " ! ⇤
" +
2 (E) ! F 8 " ! +
Lemme : " (
8↵, 2 (⌃ [ V )⇤ , 8u 2 ⌃⇤ , 3 T ⇤F ! T 9 " ! (
" )
1. si
u
! ↵ dans B alors ↵ !r u dans G
⇤ 4 F ! T 10 " ! )
" id
⇤
2. si ↵ !r u dans G et / (⌃ [ V )⇤ ⌃ alors
2
u
! ↵ dans B 5 E+T ! E 11 " ! id
"
6 T ! E
Corollaire :
L’automate LR reconnaı̂t le langage LG (S)
Conflits
reduce/reduce : (3,4) : on choisit 3
Exercice : (5,6) : on choisit 5
Transformer l’automate LR en un automate à pile classique. shift/reduce : {1,2,3,4} contre {7,8,9,10,11} : on choisit reduce
{5,6} contre 7 : on choisit shift (priorité de ⇤ sur +)
{5,6} contre {8,9,10,11} : on choisit reduce
La grammaire G2 est non ambiguë : lors d’un conflit, si on fait le mauvais choix,
on ne peut pas prolonger en un calcul acceptant.
153/197 154/197
k-conflits et grammaires LR(k) k-conflits

Définition : (Rappel) First
(
w si |w|  k Exemples :
Pour w 2 ⌃⇤ et k 0, on définit Firstk (w) =
w[k] sinon. I La grammaire G1 n’a aucun 0-conflit (il faut réduire dès que possible).
I La grammaire G3 : E ! E + E | E ⇤ E | (E) | id a des k-conflits pour tout k.
Définition : k-conflits
I Un k-conflit shift/reduce est un tuple (x, ↵, w, av) tel qu’il existe Exercice :
2 (⌃ [ V )⇤ et deux calculs dans B : I Montrer que la grammaire G2 n’a aucun 1-conflit.
" w a v
↵ ! x !
⇤ S et ↵ ! ↵a !
⇤ S Proposition : k-conflits
reduce shift
avec Firstk (w) = Firstk (av). Une grammaire n’a pas de k-conflit (shift/reduce ou reduce/reduce) si et seulement
0 0 0 si 9
I Un k-conflit reduce/reduce est un tuple (x, ↵, w, x , ↵ , w ) tel qu’il existe ⇤ 1 >
S !r xw !r ↵w =
, 0 2 (⌃ [ V )⇤ et deux calculs dans B : ⇤ 1
S !r !r ↵w 0 =) = xw0
" " w0
>
;
↵ ! x w⇤! S et 0 0
↵ ! 0 0
x ⇤! S Firstk (w) = Firstk (w0 )
reduce reduce
0 0
avec ↵ = ↵ , Firstk (w) = Firstk (w0 ) et (x, ↵) 6= (x0 , ↵0 ).
155/197 156/197
Grammaires augmentées Grammaires LR(k)
Remarque :
Pour une grammaire LR(0) il faut aussi pouvoir décider si on doit s’arrêter sans
regarder s’il reste des lettres à lire. Remarques :
C’est le cas pour la grammaire G1 : on s’arrête si la pile est exactement S.
1. Toute grammaire LR(k) engendre un langage déterministe.
Ce n’est pas le cas pour la grammaire S ! Sa | a qui n’a pourtant aucun 0-conflit.
Formellement, cette grammaire doit donc être LR(1) et pas LR(0). 2. Tout langage déterministe peut être engendré par une grammaire LR(1).
3. La hiérarchie des grammaires LR(k) est stricte :
Définition : Grammaire augmentée Pour tout k > 0 il existe une grammaire LR(k) qui n’est pas LR(k 1).
Soit G = (⌃, V, P, S) une grammaire. 4. Étant donnée une grammaire G, on ne peut pas décider s’il existe une entier k
La grammaire augmentée de G est G0 = (⌃, V ] {S 0 }, P ] {S 0 ! S}, S 0 ). tel que G soit LR(k).
5. Toute grammaire LL(k) est une grammaire LR(k).
Définition : Grammaire LR(k) 6. On peut décider si une grammaire LR(k) est aussi LL(k).
0
Une grammaire G est LR(k) si sa grammaire augmentée G n’a aucun k-conflit. 7. Étant donnée une grammaire LR(k) G, on ne peut pas décider s’il existe n tel
que G soit LL(n).
Remarque :
+
Soit G une grammaire sans dérivation du type S ! S et k > 0.
La grammaire G n’a aucun k-conflit si et seulement si G0 n’a aucun k-conflit.
157/197 158/197
Analyseur LR(k) Analyseur SLR

Exemple : Analyseur SLR pour G4
Définition : 0 : S0 ! S 1 : S ! SaSb 2: S!"
0
Soit G = (⌃, V, P, S ) une grammaire augmentée.
Un analyseur LR(k) pour G est un automate à pile Ak défini par Analyseur action goto
I un automate des contextes (fini et déterministe) : Ck = (Q, ⌃ [ V, q0 , goto) SLR a b " S
0: " r2 r2 r2 1
I une table des actions : pour q 2 Q et v 2 ⌃k ,
1: S s2 accept
action(q, v) ✓ {accept, shift} [ {reduceA!↵ | A ! ↵ 2 P } 2 : Sa r2 r2 r2 3
3 : SaS s2 s4
Soit ( , w) une configuration de Ak où est le contexte (contenu de la pile) et w 4 : SaSb r1 r1 r1
le mot qui reste à lire.
si : shift and goto i
Dans la configuration ( , w), Ak e↵ectue une action(goto(q0 , ), Firstk (w)).
rj : reduce with rule j.
Si l’ensemble des actions est vide, il déclare une erreur de syntaxe.
S a S b
0|ε 1|S 2 | Sa 3 | SaS 4 | SaSb
a
159/197 160/197
Analyseur LR(k) Analyseur SLR (Simple LR)
Définition : 0-item
Remarques : I Un 0-item est une règle pointée : A ! ↵1 .↵2 avec A ! ↵1 ↵2 2 P .
I Pour éviter de calculer goto(q0 , ) à chaque transition, on mémorise les états I Le 0-item A ! ↵1 .↵2 est valide dans le contexte si = ↵1
intermédiaires sur la pile : et s’il existe dans G une dérivation droite :
Si = 1 · · · k alors la pile est en fait le calcul de l’automate :
⇤
S 0 !r Aw
q0 1 q1 · · · k qk
ou de façon équivalente, s’il existe dans l’automate shift/reduce B un calcul
avec qi+1 = goto(qi , i+1 ).
" w
Initialement, la pile est donc q0 . ↵2 = ↵ 1 ↵ 2 ! A ! S0
reduce ⇤
I Lors d’un shift(a) on empile a puis goto(qk , a)
I Lors d’un reduceA!↵ on dépile 2|↵| symboles et on empile A puis I On note V0 ( ) l’ensemble des 0-items valides pour .
goto(qk |↵| , A).
I Lors d’un reduceA!↵ , ↵ sera toujours un suffixe de . Remarque :
I Les symboles 1, . . . , k sont en fait inutiles, il suffit d’avoir la pile des états I Si A ! ↵1 .a↵2 2 V0 ( ) alors l’action shifta est utile dans le contexte .
q0 , . . . , q k . I Si A ! ↵. 2 V0 ( ) alors l’action reduceA!↵ est utile dans le contexte .
L’automate des contextes C0 calcule les 0-items valides.
161/197 162/197
Calcul des 0-items valides Automate des contextes

Définition : Clôture
Définition : Automate des contextes SLR
Soit W un ensemble de 0-items.
A ! ↵1 .B↵2 2 W , B ! 2P L’automate C0 = (Q, ⌃ [ V, q0 , goto) est définit par
I Règle de clôture :
B!. 2W I Q est un sous-ensemble des ensembles de 0-items
I On note clot(W ) la clôture de W . I q0 = clot({S 0 ! .S})
I goto est déjà défini.
Lemme : Clôture (G réduite) On ne considère que les états accessibles.
Pour tout 2 (⌃ [ V )⇤ , l’ensemble V0 ( ) est clos.
Proposition : Automate des contextes (G réduite)
Définition : goto L’automate C0 calcule les 0-items valides : pour tout 2 (⌃ [ V )⇤ on a
Soit W un ensemble de 0-items et x 2 ⌃ [ V .
V0 ( ) = goto(q0 , )
goto(W, x) = clot({A ! ↵1 x.↵2 | A ! ↵1 .x↵2 2 W })
Exemple : Automate C0 des contextes SLR de G4
Lemme : goto (G réduite)
0 : S0 ! S 1 : S ! SaSb 2: S!"
⇤
Pour tout 2 (⌃ [ V ) , on a goto(V0 ( ), x) ✓ V0 ( x).
163/197 164/197
Table des actions Analyseur SLR
Exemple : Analyseur SLR pour G4
Définition : Table des actions de l’analyseur SLR A0 0 : S0 ! S 1 : S ! SaSb 2: S!"
Soit W un ensemble de 0-items, a 2 ⌃ et u 2 ⌃1 : Follow1 (S 0 ) = {"} Follow1 (S) = {", a, b}
shift 2 action(W, a) si W contient un 0-item du type A ! ↵1 .a↵2

Analyseur action goto
reduceA!↵ 2 action(W, u) si A ! ↵. 2 W et u 2 Follow1 (A) et A 6= S 0 SLR a b " S
accept 2 action(W, ") si S 0 ! S. 2 W 0: " r2 r2 r2 1
1: S s2 accept
Remarque : les actions ne sont utiles que pour les états accessibles de l’automate
2 : Sa r2 r2 r2 3
des contextes C0 .
3 : SaS s2 s4
Définition : Grammaire SLR 4 : SaSb r1 r1 r1
Une grammaire G est SLR s’il n’y a pas de conflit dans la table action de son si : shift and goto i
analyseur SLR rj : reduce with rule j.
S a S b
0|ε 1|S 2 | Sa 3 | SaS 4 | SaSb
a
165/197 166/197
Analyse SLR Analyse SLR
Proposition : Correction
Soit A0 l’analyseur SLR de G = (⌃, V, P, S 0 ). On a L(A0 ) = LG (S 0 ).
Exercice :
Calculer l’automate des contextes et la table des actions pour la grammaire G2 : Preuve
Soit B l’analyseur shift/reduce général de la grammaire G.
0 : E0 ! E 1: E !E+T 2: E!T
Tout calcul de A0 est un calcul de B : L(A0 ) ✓ L(B) = LG (S 0 ).
3: T !T ⇤F 4: T !F w
Tout calcul acceptant " ! S 0 de B est un calcul de A0 : L(A0 ) ◆ L(B) = LG (S 0 ).
5 : F ! (E) 6 : F ! id ⇤
En déduire que G2 est une grammaire SLR. Remarque : non déterminisme

Si G n’est pas SLR, l’analyseur A0 est non déterministe : plusieurs actions peuvent
être possibles dans une configuration ( , w).
On a quand même L(A0 ) = LG (S 0 ).
167/197 168/197
Analyseur SLR Grammaires et génération du code
Exemple : Analyseur SLR pour G5 Remarque : Grammaires équivalentes
0 La grammaire G5
0: S !S 1 : S ! L := R 2: S!R
3 : L ! ⇤R 4 : L ! id 5: R!L 0 : S0 ! S 1 : S ! L := R 2: S!R
0
Follow1 (S ) = Follow1 (S) = {"} Follow1 (R) = Follow1 (L) = {", :=} 3 : L ! ⇤R 4 : L ! id 5: R!L
Analyseur action goto est équivalente à la grammaire G05

SLR id ⇤ := " S L R 0 : S0 ! S 1 : S ! L := L 2: S!L
0: " s5 s4 1 2 3 3 : L ! ⇤L 4 : L ! id
1: S accept
2: L s 6 | r5 r5 et elle engendre même un langage rationnel donc elle est équivalente à une grammaire
linéaire (gauche ou droite).
3: R r2
Cependant G5 est mieux adaptée à la génération du code.
4: ⇤ s5 s4 8 7
Elle explicite la di↵érence entre adresse (L) et valeur (R) et les règles permettent de
5 : id r4 r4
générer le code correspondant :
6 : L := s5 s4 8 9
7 : ⇤R r3 r3
I L ! id : obtenir l’adresse de la variable
8 : ⇤L r5 r5 I R ! L : obtenir la valeur contenue à une adresse
9 : L := R r1 I L ! ⇤R : convertir valeur en adresse.
Un conflit shift/reduce. Exemple : abres syntaxiques pour les instructions id := id et ⇤id := ⇤id.
169/197 170/197
Grammaire ambiguë IF THEN ELSE

Exemple : Table SLR pour G3
0 : E0 ! E 1: E !E+E 2: E !E⇤E
3 : E ! (E) 4 : E ! id
Remarque :
Follow1 (E) = {", +, ⇤, )} L’instruction if then else présente aussi une ambiguı̈té classique.
id + ⇤ ( ) " E Considérons la grammaire

0: " s3 s2 1
1: E s4 s5 accept I ! if C then I else I | if C then I | A
2: ( s3 s2 6 Le mot if C then if C then A else A admet deux arbres de dérivation.
3: id r4 r4 r4 r4
4: E+ s3 s2 7 L’automate LR présente un conflit shift/reduce.
5: E⇤ s3 s2 8 On choisit le shift : un else se rapporte au dernier if qui n’a pas de else.
6: (E s4 s5 s9
7: E+E r1 | s 4 r1 | s 5 r1 r1
8: E⇤E r2 | s 4 r2 | s 5 r2 r2
9: (E) r3 r3 r3 r3
4 conflits shift/reduce que l’on résout grâce aux règles de priorité et d’associativité.
171/197 172/197
Insuffisance de l’analyse SLR Analyseur LR(1)
Définition : 1-item
I 1-item : [A ! ↵1 .↵2 , u] avec A ! ↵1 ↵2 2 P et u 2 ⌃1 .
I Le 1-item [A ! ↵1 .↵2 , u] est valide dans le contexte si = ↵1
Remarque : et s’il existe dans G une dérivation droite :
Supposons que reduceA!↵ 2 action(V0 ( ), a), i.e., ⇤
S 0 !r Aw avec u = First1 (w)
A ! ↵. 2 V0 ( ) et a 2 Follow1 (A)
ou de façon équivalente, s’il existe dans l’automate shift/reduce B un calcul
0 ⇤
Mais que pour tout S !r Aw on ait a 2 / First1 (w) alors, ↵2 = ↵ 1 ↵ 2
" w
! A ! S0 avec u = First1 (w)
reduce ⇤
l’action reduceA!↵ est inutile pour (V0 ( ), a).
cf. preuve de la proposition Correction. I On note V1 ( ) l’ensemble des 1-items valides pour .
Ceci est dû à l’imprécision de Follow1 (A). Remarque :
I Si [A ! ↵1 .↵2 , u] 2 V1 ( ) alors A ! ↵1 .↵2 2 V0 ( ) et u 2 Follow1 (A).
I Si A ! ↵1 .↵2 2 V0 ( ) alors il existe u 2 ⌃1 tel que [A ! ↵1 .↵2 , u] 2 V1 ( ).
I Si [A ! ↵., u] 2 V1 ( ) alors l’action reduceA!↵ est utile dans une
configuration ( , w) avec u = First1 (w).
173/197 174/197
Calcul des 1-items valides Automate des contextes

Définition : Automate des contextes
Définition : Clôture L’automate C1 = (Q1 , ⌃ [ V, q0 , goto) est définit par
Soit W un ensemble de 1-items. I Q1 est un sous-ensemble des ensembles de 1-items
[A ! ↵1 .B↵2 , u] 2 W , B ! 2 P , v 2 First1 (↵2 u)
I Règle de clôture : I q0 = clot({[S 0 ! .S, "]})
[B ! . , v] 2 W
I goto est déjà défini.
I On note clot(W ) la clôture de W .
On ne considère que les états accessibles.
Lemme : Clôture
Proposition : Automate des contextes
Pour tout 2 (⌃ [ V )⇤ , l’ensemble V1 ( ) est clos.
L’automate C1 calcule les 1-items valides : pour tout 2 (⌃ [ V )⇤ on a
Définition : goto V1 ( ) = goto(q0 , )
Soit W un ensemble de 1-items et x 2 ⌃ [ V .
Exemple :
goto(W, x) = clot({[A ! ↵x.↵2 , u] | [A ! ↵.x↵2 , u] 2 W })
Calcul de l’automate des contextes C1 pour la grammaire G5 .
Lemme : goto
Exercices :
Pour tout 2 (⌃ [ V )⇤ , on a goto(V1 ( ), x) ✓ V1 ( x).
1. Calcul de l’automate des contextes C1 pour la grammaire G2 .
2. Calcul de l’automate des contextes C1 pour la grammaire G4 .
175/197 176/197
Table des actions Analyseur LR(1)
Exemple : Analyseur LR(1) pour G4
Définition : Table des actions
0 : S0 ! S 1 : S ! SaSb 2: S!"
Soit W un ensemble de 1-items, a 2 ⌃ et u 2 ⌃1 :
shift 2 action(W, a) si W contient un 1-item du type [A ! ↵1 .a↵2 , u] Analyseur action goto
LR(1) a b " S
reduceA!↵ 2 action(W, u) si [A ! ↵., u] 2 W et A 6= S 0
0: " r2 r2 1
accept 2 action(W, ") si [S 0 ! S., "] 2 W 1: S s2 accept
Remarque : les actions ne sont utiles que pour les états accessibles de l’automate 2 : Sa r2 r2 3
des contextes. 3 : SaS s5 s4
4 : SaSb r1 r1
Exemple : 5 : SaSa r2 r2 6
Tables action et goto pour l’analyseur LR(1) de G5 . 6 : SaSaS s5 s7
7 : SaSaSb r1 r1
Exercices : si : shift and goto i rj : reduce with rule j
1. Tables action et goto pour l’analyseur LR(1) de G2 .
b 4
2. Tables action et goto pour l’analyseur LR(1) de G4 . S a S
0 1 2 3 a S b
5 6 7
a
177/197 178/197
Analyseur LR(1) Analyse LR(1)

Exemple : Analyseur LR(1) pour G5 Lemme : A0 versus A1
Analyseur action goto I Si [A ! ↵1 .↵2 , u] 2 V1 ( ) alors A ! ↵1 .↵2 2 V0 ( ) et u 2 Follow1 (A).
LR(1) id ⇤ := " S L R I Si A ! ↵1 .↵2 2 V0 ( ) alors il existe u 2 ⌃1 tel que [A ! ↵1 .↵2 , u] 2 V1 ( ).
0: " s5 s4 1 2 3
I A0 et A1 ont les mêmes actions shift.
1: S accept
2: L s6 r5 I Les actions reduce de A1 sont des actions de A0 .
3: R r2
4: ⇤ s5 s4 8 7 Proposition : Correction
5 : id r4 r4 Soit A1 l’analyseur LR(1) de G = (⌃, V, P, S 0 ). On a L(A1 ) = LG (S 0 ).
6 : L := s12 s11 10 9
7 : ⇤R r3 r3 Proposition :
8 : ⇤L r5 r5 Une grammaire G est LR(1) si et seulement si il n’y a pas de conflit dans la table
9 : L := R r1 action de son analyseur LR(1)
10 : L := L r5
11 : L := ⇤ s12 s11 10 13 Corollaire :
12 : L := id r4
On peut décider si une grammaire G est LR(1).
13 : L := ⇤R r3
179/197 180/197
Plan Bibliographie
Introduction
Automates d’arbres [6] Jean Berstel.

Transduction and context free languages.
Teubner, 1979.
Grammaires
[11] Jean-Éric Pin.
Automates finis et applications.
Langages algébriques Polycopié du cours à l’École Polytechnique, 2004.
[13] Jacques Sakarovitch.
Automates à pile Éléments de théorie des automates.
Vuibert informatique, 2003.
Analyse syntaxique
8 Fonctions séquentielles
Définitions et exemples
Composition
Résiduels et normalisation 181/197 182/197
Minimisation
Automates séquentiels purs fonctions séquentielles pures

Définition : Automates séquentiels purs (Mealy machine)
A = (Q, A, B, q0 , , ') où Définition : fonctions séquentielles pures
I Q ensemble fini d’états et q0 2 Q état initial, Une fonction f : A⇤ ! B ⇤ est séquentielle pure s’il existe un automate séquentiel
I A et B alphabets d’entrée et de sortie, pur A qui la réalise : f = [[A]].
I : Q ⇥ A ! Q fonction partielle de transition,
Exemples :
I ' : Q ⇥ A ! B ⇤ fonction partielle de sortie avec dom(') = dom( ).
1. Transformation d’un texte en majuscules.
Remarque : L’automate “d’entrée” (Q, A, q0 , ) est déterministe.
2. Remplacement d’une séquence d’espaces ou tabulations par un seul espace.
Définition : Sémantique : [[A]] : A ! B ⇤ ⇤ 3. Codage et décodage avec le code préfixe défini par
On étend et ' à Q ⇥ A⇤ par a 7! 0000 c 7! 001 e 7! 011 g 7! 11
I (q, ") = q et (q, ua) = ( (q, u), a) b 7! 0001 d 7! 010 f 7! 10
I '(q, ") = " et '(q, ua) = '(q, u)'( (q, u), a)
4. Division par 3 d’un entier écrit en binaire en commençant par le bit de poids
et la sémantique de A est la fonction partielle [[A]] : A⇤ ! B ⇤ définie par
fort. Qu’en est-il si on commence avec le bit de poids faible ?
I [[A]](u) = '(q0 , u).
Noter que [[A]](") = "
183/197 184/197
Automates séquentiels fonctions séquentielles
Définition : Automates séquentiels
A = (Q, A, B, q0 , , ', m, ⇢) où
I A = (Q, A, B, q0 , , ') est un automate séquentiel pur,
Définition : fonctions séquentielles
I m 2 B ⇤ est le préfixe initial,
Une fonction f : A⇤ ! B ⇤ est séquentielle s’il existe un automate séquentiel A qui
I ⇢ : Q ! B ⇤ est la fonction partielle finale.
la réalise : f = [[A]].
On appelle état final un état dans dom(⇢).
La sémantique de A est la fonction partielle [[A]] : A⇤ ! B ⇤ définie par Lemme :
I [[A]](u) = m'(q0 , u)⇢( (q0 , u)). Une fonction séquentielle peut être réalisée par un automate séquentiel ayant un
préfixe initial vide (m = ").
Exemples :
1. La fonction f : A⇤ ! A⇤ définie par f (u) = u(ab) 1
. Proposition :
2. Addition de deux entiers écrits en binaire en commençant par le bit de poids Une fonction séquentielle peut être réalisée par un automate émondé, i.e., tel que
faible. 8p 2 Q, 9u, v 2 A⇤ tels que (q0 , u) = p et (p, v) 2 dom(⇢).
3. La multiplication par 3 d’un entier écrit en binaire en commençant par le bit
de poids faible.
4. Le décodage par un code à délai de déchi↵rage borné.
Ces fonctions sont-elles séquentielles pures ?
185/197 186/197
Composition Produit en couronne

Définition : Produit en couronne
Soient A = (Q, A, B, q0 , , ', m, ⇢) et A0 = (Q0 , B, C, q00 , 0 , '0 , m0 , ⇢0 ) deux auto-
Théorème : Composition mates séquentiels.
Le produit en couronne A0 A = (Q00 , A, C, q000 , 00 , '00 , m00 , ⇢00 ) est défini par
Soient f : A⇤ ! B ⇤ et g : B ⇤ ! C ⇤ deux fonctions partielles.
I Q00 = Q ⇥ Q0 , q000 = (q0 , 0 (q00 , m)) et m00 = m0 '0 (q00 , m),
1. Si f et g sont séquentielles alors g f : A⇤ ! C ⇤ est aussi séquentielle.
00
I ((p, p0 ), a) = ( (p, a), 0 (p0 , '(p, a))),
2. Si f et g sont séquentielles pures alors g f est aussi séquentielle pure.
I ' ((p, p0 ), a) = '0 (p0 , '(p, a)),
00
Exemple : Multiplication par 5 I ⇢00 ((p, p0 )) = '0 (p0 , ⇢(p))⇢0 ( 0 (p0 , ⇢(p))).
2
Dans cet exemple, A = C = {0, 1}, B = {0, 1} et les mots représentent des entiers
codés en binaire en commençant par le bit de poids faible. Lemme : Extension à A⇤
On considère les fonctions séquentielles f : A⇤ ! B ⇤ et g : B ⇤ ! C ⇤ définies par Pour tout u 2 A⇤ , on a
f (n) = (n, 4n), i.e., f (u) = (u00, 00u) et g(n, m) = n + m. I 00
((p, p0 ), u) = ( (p, u), 0 (p0 , '(p, u))),
La fonction g f code la multiplication par 5. I '00 ((p, p0 ), u) = '0 (p0 , '(p, u)),
Construire les automates séquentiels réalisant f et g.
En déduire un automate séquentiel pour g f .
Preuve (Composition)
1. Si f et g sont réalisées par A et A0 alors g f est réalisée par A0 A.
2. Si A et A0 sont purs alors A0 A est pur.
187/197 188/197
Fonct. séquentielles et lang. rationnels Plus grand préfixe commun
Définition :
Définition : Fonction caractéristique I Tout sous ensemble ; = 6 X ✓ B ⇤ admet un plus grand préfixe commun,
⇤
Soit L ✓ A un langage. La fonction caractéristique de L est la fonction totale i.e., une borne inférieure pour l’ordre
V préfixe.
1L : A⇤ ! {0, 1} définie par 1L (u) = 1 si et seulement si u 2 L. Cette borne inférieure est notée X.
I que ; n’admet pas de plus grand préfixe commun.
Noter V
Théorème : Donc ; n’est pas défini.
Un langage L ✓ A⇤ est rationnel si et seulement si sa fonction caractéristique 1L
est séquentielle. Remarque :
1. Soit u 2 B ⇤ et ; =
6 X ✓ B⇤.
Corollaire : Image inverse V V
I u · XV= u · XV
1 1 V
Soient f : A⇤ ! B ⇤ une fonction séquentielle. I si u  X alors u ·X =u · X
Si L ✓ B ⇤ est rationnel alors f 1 (L) est rationnel. 2. Soit f : A ! B une fonction partielle, on a f (A⇤ ) = {f (u) | u 2 dom(f )}.
⇤ ⇤
V
Théorème : Image directe Donc f (A⇤ ) est défini si dom(f ) 6= ;.
Soient f : A⇤ ! B ⇤ une fonction séquentielle. Exemple :

Si L ✓ A⇤ est rationnel alors f (L) est rationnel.
Soit f : A⇤ ! A⇤ la fonction
V partielle définie par f (w) = w(ab) 1
.
Pour u 2 A⇤ , calculer f (uA⇤ ).
189/197 190/197
Résiduels Normalisation
Définition : Résiduels
Soit f : A⇤ ! B ⇤ une fonction partielle et soit u 2 A⇤ . Exemple :
Le résiduel fu : A⇤ ! B ⇤ est défini par Donner un automate séquentiel réalisant la fonction f : A⇤ ! A⇤ définie par
1
I dom(fu ) = u dom(f ) et f (a2n b) = (ab)n a.
V
I fu (v) = ( f (uA⇤ )) 1 f (uv) pour uv 2 dom(f ). Cet automate devra sortir les lettres du résultat le plus rapidement possible.
V
f (uA⇤ ) représente tout ce qu’on peut écrire si on sait que la donnée commence Définition : Automate normalisé
par u. Le résiduel fu (v) est donc ce qui reste à écrire si la donnée est uv.
Intuitivement, un automate est normalisé s’il écrit son résultat au plus tôt.
Exemple : Soit A = (Q, A, B, q0 , , ', m, ⇢) un automate séquentiel et p 2 Q.
V
Calculer les résiduels de la fonction f : A⇤ ! A⇤ définie par f (w) = w(ab) 1
. On définit Ap = (Q, A, B, p, , ', ", ⇢) et mp = [[Ap ]](A⇤ ) si [[Ap ]](A⇤ ) 6= ;.
L’automate A est normalisé si pour tout p 2 Q, [[Ap ]](A⇤ ) = ; ou mp = ".
Lemme : Composition
Exercice : E↵ectivité
Soient u, v 2 A⇤ . On a fuv = (fu )v , i.e.,V
dom(fuv ) = v 1 dom(fu ) et fuv (w) = ( fu (vA⇤ )) 1
fu (vw). Étant donné un automate séquentiel A, on peut calculer les mp en temps quadratique
(cf. DM1 2006).
Théorème : Caractérisation par résiduels
f : A⇤ ! B ⇤ est séquentielle si et seulement si elle a un nombre fini de résiduels.
191/197 192/197
Normalisation Séquentielle et séquentielle pure
Proposition : Normalisation
Définition :
Tout automate séquentiel est équivalent à un automate séquentiel normalisé, qui
Une fonction partielle f : A⇤ ! B ⇤ préserve les préfixes si
peut être choisi émondé ou complet.
I son domaine est préfixiel : u  v et v 2 dom(f ) implique u 2 dom(f ),
Preuve I et elle est croissante : u  v et v 2 dom(f ) implique f (u)  f (v).
Soit A = (Q, A, B, q0 , , ', m, ⇢) un automate séquentiel émondé
(donc mp est bien défini pour tous p 2 Q).
Proposition :
On définit A0 = (Q, A, B, q0 , , '0 , m0 , ⇢0 ) par : 1. Une fonction séquentielle pure préserve les préfixes.
I m0 = mm
V 2. Soit f : A⇤ ! B ⇤ une fonction séquentielle. Si f (") = " et f préserve les
q0 = [[A]](A⇤ ),
préfixes alors f est séquentielle pure.
I '0 (p, a) = mp 1 ('(p, a)m (p,a) ) si (p, a) 2 dom(') = dom( )
I ⇢0 (p) = mp 1 ⇢(p) si p 2 dom(⇢) Preuve
0 0
On vérifie que A est normalisé et [[A ]] = [[A]]. L’automate normalisé émondé d’une fonction séquentielle f qui préserve les préfixes
et telle que f (") = " est un automate séquentiel pur.
Pour obtenir un automate complet, il suffit d’ajouter un état puits.
193/197 194/197
Résiduels Automate des résiduels

L’automate des résiduels de f est R = (Q, A, B, q0 , , ', m, ⇢) où
I Q = {fu | u 2 A⇤ } (supposé fini pour la réciproque du théorème),
V
I q0 = f" et m = f (A⇤ ) si dom(f ) 6= ;, et m = " sinon,
Théorème : Caractérisation par résiduels I (fu , a) = (fu )a = fua ,
Une fonction f : A⇤ ! B ⇤ est séquentielle si et seulement si elle a un nombre fini V
I '(fu , a) = fu (aA⇤ ) si dom(fua ) 6= ;, et '(fu , a) = " sinon,
de résiduels.
I ⇢(fu ) = fu (") si " 2 dom(fu ), et fu 2
/ dom(⇢) sinon.
Lemme :
Soit A = (Q, A, B, q0 , , ', m, ⇢) un automate normalisé complet. Lemme :
Soit u 2 A⇤ et p = (q0 , u). Alors fu = [[Ap ]]. 1. Soient u, v 2 A⇤ . On a (fu , v) = fuv .
V
On en déduit qu’une fonction séquentielle réalisée par A a au plus |Q| résiduels. 2. Soient u, v 2 A⇤ . On a '(fu , v) = fu (vA⇤ ) si dom(fuv ) 6= ;.
3. Soit u 2 A⇤ . On a fu = [[Rfu ]].
Exemple : 4. f = [[R]].
La fonction f : A⇤ ! A⇤ définie par f (w) = ww est-elle séquentielle ? 5. L’automate des résiduels est normalisé, accessible et complet.
Exemple :
Calculer l’automate des résiduels de la fonction multiplication par 5 où les entiers
sont codés en binaire en commençant avec le bit de poids faible.
195/197 196/197
Minimisation
Théorème : Automate minimal
Soit f : A⇤ ! B ⇤ une fonction séquentielle.
L’automate des résiduels de f , noté Rf , est minimal parmi les automates normalisés
et complets qui réalisent f .
Construction de l’automate minimal

Soit A = (Q, A, B, q0 , , ', m, ⇢) un automate réalisant une fonction f .
I émonder puis normaliser puis compléter l’automate.
I quotienter l’automate par l’équivalence définie par p ⇠ q si [[Ap ]] = [[Aq ]].
Cette équivalence se calcule par raffinement :
I p ⇠0 q si ⇢(p) = ⇢(q).
I p ⇠n+1 q si p ⇠n q et 8a 2 A, (p, a) ⇠n (q, a) et '(p, a) = '(q, a).
Exemple :
Minimiser l’automate naturel de f : A⇤ ! A⇤ définie par f (w) = w(ab) 1
.
197/197

Langages Formels

Transféré par

Droits d'auteur :

Formats disponibles

Langages Formels

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Langages Formels

Transféré par

Droits d'auteur :

Formats disponibles

Plan

Grammaires 7/197 8/197

A ou ⌃ : alphabet (ensemble fini). Ordres partiels :

|u| : longueur du mot u. Théorème : Higman

Ensemblistes : union, intersection, complément, di↵érence, . . .

avec qi = (qi 1 , ai ) pour tout 0 < i  n.

Automates non déterministes Automates non déterministes

Décision Propriétés de fermeture

Propriétés de fermeture Propriétés de fermeture

Langages rationnels Langages rationnels

Syntaxe pour représenter des langages.

Critères de reconnaissabilité Critères de reconnaissabilité

Y a-t-il des langages non reconnaissables ? Lemme : itération

Critères de reconnaissabilité Minimisation

Exemple : automates D ou ND pour a⇤ .

Équivalence de Nerode Automate minimal

L’équivalence de Nerode est une congruence. Corollaire :

Logique sur les mots Logique sur les mots

Congruences Morphismes et Congruences

Théorème : est aussi reconnaissable.

Apériodiques et sans étoile Sans étoile et sans compteur

53/197 Langages algébriques 54/197

Bibliographie Analyse syntaxique Arbres

((x ! y) ^ (¬y _ ¬z)) ^ (z _ ¬x)

2. Arbre représentant le programme

Automates d’arbres Grammaires et automates d’arbres

Exemples : Donner des automates pour les langages d’arbres suivants :

Arbres et termes Arbres et termes

Automates déterministes Substitutions d’arbres

Congruences Congruence syntaxique

L\s = {r 2 Tp,2 (⌃) | r · s 2 L}.

Lemme : Lemme : Equivalence de Nerode et congruence syntaxique

Automate minimal Calcul de l’équivalence de Nerode

1. AL est isomorphe au quotient de Nerode A/⇠.

Logique sur les arbres Logique sur les arbres

LV (') = {T 2 Tp (⌃V ) | T = (t, ) est valide et (t, ) |= '}

Théorème : Thatcher and Wright 1968 Langages reconnaissables

81/197 Analyse syntaxique 82/197

1: S ! DXaF 3 : XF ! Y F 5 : DY ! DX 7 : aZ ! Za Théorème : Type 0 [9, Thm 9.3 & 9.4]

Définition : Grammaire contextuelle (type 1, context-sensitive) Définition : Forme normale (context-sensitive/contextuelle)

2 : S ! aa 4 : T ! aa 6 : XaF ! aaF 8 : DaaF ! aaaa

Grammaires contextuelles Grammaires algébriques

Exercices : Lemme : fondamental

Hiérarchie de Chomsky Bibliographie

Exercice : if then else

Lemme d’Ogden Lemme d’Ogden

Plus fort que le théorème de Bar-Hillel, Perles, Shamir. Exercice :

Définition : Substitutions algébriques Soient A, B, C trois alphabets, K 2 Rat(C ⇤ ) et ' : C ⇤ ! A⇤ et : C ⇤ ! B ⇤ deux

Transductions rationnelles Grammaires réduites

Théorème : Nivat, 1968 Corollaire : Soit G = (⌃, V, P, S) une grammaire

Problèmes décidables Problèmes indécidables

La difficulté est d’éliminer la récursivité gauche des règles.

Forme normale de Greibach Équations algébriques

Équations algébriques Plan

Exemple : 6 Automates à pile

Propriétés fondamentales Acceptation généralisée

Proposition : Acceptation généralisée

Accessibilité et mots de pile Accessibilité et mots de pile (Preuve)

Corollaire : C(pg) = Clot(K + · pg) \ QZ ⇤ .