Théorie des langages
Anca Muscholl
LaBRI Bordeaux
Cours licence 2006/07
1/14
Organisation
1 Cours : 6 séances (fin mi-mars) ; TD : 11 séances
2 Contrôle continu : 4 interrogations et/ou DM (3 meilleures notes comptent)
3 Note finale 0, 75 exam + 0, 25 max (exam,CC)
4 Notes de cours, feuilles de TD et références : voir
http ://www.labri.fr/perso/anca/Langages.html
2/14
1 Automates finis et mots
Plan
2 Automates finis et arbres
3 Automates à pile
Motivations
• Description et analyse de langages (traitement du texte, codes, langages
de programmation, langages naturels, . . . )
• Modèles de calcul, conception d’algorithmes
Bibliographie
• J.E. Hopcroft, J.D. Ullman. Introduction to automata theory, languages
and computation.
Addison-Wesley, 1979.
• M. Sipser. Introduction to the theory of computation.
PWS Publishing Company, 1996.
• J. Berstel. Automates et grammaires (notes de cours,
Univ. Marne-la-Vallée, 2005).
3/14
Définitions
Mots
• Alphabet A, B, Σ, Γ : ensemble fini de lettres (symboles) a, b, α, β, . . .
• Mot : suite finie de lettres w = a1 a2 · · · an (ai ∈ Σ) ; longueur n
• Mot vide (longueur 0)
• Concaténation (produit) de 2 mots : juxtaposition (associative)
• Σ∗ : ensemble des mots sur l’alphabet Σ
(Σ∗ , ·, ) monoïde libre (généré par Σ)
Σ+ = Σ∗ \ {} ensemble des mots non-vides
• Longueur |w| de w
• Langage (de mots) L ⊆ Σ∗ (notation L, K , X , Y , . . .)
• Opérations sur les langages (L, K ⊆ Σ∗ ) :
• opérations booléennes : union L ∪ K , intersection L ∩ K , complémentation
Lc , différence L \ K = L ∩ K c
• produit LK = {uv | u ∈ L, v ∈ K }, puissances Ln = {u1 · · · un | uk ∈ L}
• itération (étoile) L∗ = n≥0 Ln , itération stricte L+ = n>0 Ln
S S
• quotients K −1 L = {v ∈ Σ∗ | ∃u ∈ K : uv ∈ L} et LK −1
4/14
Automates finis sur les mots
Applications : Modélisation des neurones, de circuits logiques (années
’50-’60), analyse lexicale en compilation, traitement du texte
(ex. reconnaissance de motifs), modélisation de mécanismes de contrôle, . . . .
Definition
Un automate fini A = hQ, Σ, δ, I , F i sur l’alphabet Σ est composé d’un
ensemble fini d’états Q, d’une relation de transitions δ ⊆ Q × Σ × Q, d’un
ensemble I ⊆ Q d’états initiaux, et d’un ensemble F ⊆ Q d’états finaux (ou
terminaux).
• Représentation par graphes étiquetés (Σ-étiquettes sur les arcs)
0 n a ···a
• Calcul dans A (étiqueté par a0 · · · an ) : q0 −→ qn+1
(q0 , a0 , q1 )(q1 , a1 , q2 ) · · · (qn , an , qn+1 ), (qk , ak , qk+1 ) ∈ δ, ∀k
Calcul acceptant : q0 ∈ I , qn+1 ∈ F
• Langage reconnu (ou accepté) L(A) : ensemble des mots ayant un calcul
acceptant.
5/14
Langages reconnaissables
Definition
Un langage L ⊆ Σ∗ est reconnaissable (ou rationnel, ou régulier) s’il est
reconnu par un automate fini.
Rec(Σ∗ ) : ensemble des langages reconnaissables sur l’alphabet Σ
Questions
• Différents types d’automates finis : déterministes non-déterministes sans
transitions- (Définition), avec transitions-, . . . (alternants,
boustrophédons, transducteurs, etc.)
• Autres descriptions des reconnaissables (ex. méchanisme de génération :
expressions rationnelles, grammaires, logique) ? Traductions effectives ?
• Propriétés de fermeture de Rec(Σ∗ ) sous certaines opérations.
6/14
Langages reconnaissables
DFA automates déterministes (deterministic finite-state automata),
NFA automates non-déterministes (nondeterministic finite-state automata),
Déterminisation (DFA = NFA)
Tout NFA A peut être transformé en un DFA équivalent B : L(A) = L(B).
B : automate des parties (taille exponentielle)
Definition
L’ensemble Rat(Σ∗ ) des expressions rationnelles sur Σ est défini par :
• ∅ et a (a ∈ Σ) appartiennent à Rat(Σ∗ )
• Si E et F sont dans Rat(Σ∗ ), alors (E + F ), (E · F ) et E ∗ aussi.
On identifie une expression rationnelle E et le langage L(E) décrit par E.
Théorème de Kleene
Rat(Σ∗ ) = Rec(Σ∗ ), pour tout alphabet Σ.
7/14
Kleene
Théorème de Kleene
Rat(Σ∗ ) = Rec(Σ∗ ), pour tout alphabet Σ.
• Rec(Σ∗ ) −→ Rat(Σ∗ ) : algorithme de McNaughton/Yamada, système
d’équations linéaires (FOI), . . .
• Rat(Σ∗ ) −→ Rec(Σ∗ ) : opérations de fermeture de Rec(Σ∗ ) (FOI),
construction de Thomson, Glushkov, . . .
McNaughton/Yamada : Soit A = hQ = {1, . . . , n}, Σ, δ, I , F i un NFA.
(k)
L’algorithme construit les expressions rationnelles Ri,j , avec i, j ∈ Q,
k ∈ Q ∪ {0} :
(k)
Ri,j est l’ensemble des mots qui étiquetent un chemin de l’état i vers l’état j,
et qui n’utilise que les états {1, . . . , k} comme états intermédiaires.
(0)
• (Base) Ri,j = A, où A = {a ∈ Σ ∪ {} | (i, a, j) ∈ δ}
(k) (k−1) (k−1) (k−1) ∗ (k−1)
• (Induction) Ri,j = Ri,j + Ri,k (Rk,k ) Rk,j
8/14
Kleene
Rat(Σ∗ ) −→ Rec(Σ∗ )
Construction de Glushkov : NFA sans transitions
• Soit E une expression rationnelle (= mot sur Σ ∪ {, +, ·, ∗, (, )}).
• Pos(E) = ensemble des positions de E correspondant aux lettres de Σ
• On suppose que toutes les lettres de Σ dans E sont distinctes (sinon,
renommage).
• On calcule (inductivement) les ensembles suivants :
first(E) = {a ∈ Pos(E) | L(E) ∩ aΣ∗ 6= ∅,
last(E) = {a ∈ Pos(E) | L(E) ∩ Σ∗ a 6= ∅}
follow(E) = {(a, b) | L(E) ∩ Σ∗ abΣ∗ 6= ∅}
a
• On construit le DFA A = hPos(E) ∪ {q0 }, Σ, δ, q0 , F i, où q0 −→ a si
b
a ∈ first(E), et a −→ b si (a, b) ∈ follow(E) ; F = last(E) is ∈
/ L(E), et
F = last(E) ∪ {q0 } sinon.
9/14
Logique
Syntaxe
Soit Var1 = {x, y, z, . . .}, Var2 = {X , Y , Z , . . .} deux ensembles disjoints de
variables (on appelera les éléments de Var1 variables du premier ordre, et
ceux de Var2 variables du second ordre).
Les formules de MSOL (logique monadique du second ordre) sur un alphabet
Σ sont définies inductivement :
• (Base) a(x), y = x + 1, x ≤ y, x ∈ X sont des formules
• (Ind.) Si ϕ1 , ϕ2 , ϕ sont des formules, alors
ϕ1 ∧ ϕ2 , ¬ϕ, ∃x. ϕ, ∃X . ϕ
sont des formules aussi.
Formules dérivées :
ϕ1 ∨ ϕ2 = ¬(¬ϕ1 ∧ ¬ϕ2 ), ϕ1 → ϕ2 = ¬ϕ1 ∨ ϕ2 ,
∀x. ϕ = ¬(∃x. ¬ϕ), ∀X . ϕ = ¬(∃X . ¬ϕ)
10/14
Logique
Sémantique (sur les mots)
On fixe un mot w sur l’alphabet Σ (modèle). Soit n = |w|.
• Les variables de Var1 sont interprétées par des positions k ∈ {1, . . . , n} de
w. Les variables de Var2 sont interprétées par des ensembles de positions
K ⊆ {1, . . . , n} de w.
• La formule a(x) est vraie pour x = k ssi wk = a. La formule y = x + 1
(x ≤ y, respectivement) est vraie pour x = i, y = j ssij = i + 1 (ssi i ≤ j,
respectivement). La formule x ∈ X est vraie pour x = k, X = K ssi k ∈ K .
• Les connecteurs booléens ∧, ¬ ainsi que les quantificateurs ∃, ∀ ont
l’interprétation usuelle (voir FOI).
Exemples et notation
∀x∀y. (y = x + 1 → ((a(x) ∧ b(y)) ∨ (b(x) ∧ a(y))
∃X .(∀x∀y. (y = x + 1 → (x ∈ X ↔ y ∈
/ X )) ∧ 1 ∈ X ∧ max ∈ X )
On note par w ` ϕ le fait que w ∈ Σ∗ satisfait une formule ϕ (sans variable
libre) et par L(ϕ) = {w ∈ Σ∗ | w ` ϕ} le langage décrit par ϕ.
11/14
Logique
Théorème de Buechi
Pour tout NFA A il existe une formule MSOL ϕA t.q. L(A) = L(ϕA ), et
réciproquement.
NFA → MSOL :
Soit A = hQ, Σ, δ, I , F i un NFA, Q = {1, . . . , n}. On construit une formule
MSOL
ϕA = ∃X1 ∃X2 . . . ∃Xn (ψ1 ∧ ψ2 ∧ p3 )
• ψ1 dit que (X1 , . . . , Xn ) est une partition de l’ensemble des positions :
Xk correspond aux positions étiquetées par l’état k dans un calcul
acceptant fixé (état après la transition)
W
• ψ2 = ∀x. (x 6= max → (i,a,j)∈δ (x ∈ Xi ∧ x + 1 ∈ Xj ∧ a(x + 1)))
(“l’étiquetage par états représente un calcul”)
W W
• ψ3 = i∈I ,(i,a,k)∈δ (1 ∈ Xk ∧ a(1)) ∧ j∈F max ∈ Xj (“le calcul est
acceptant”)
12/14
Propriétés de fermeture
Proposition
La classe Rec(Σ∗ ) est fermée par
• les opérations booléennes,
• le produit et l’itération,
• préfixe, suffixe et facteur,
• quotient gauche/droit : si L est reconnaissable et K quelconque, alors
K −1 L et LK −1 le sont aussi.
• morphisme, substitution rationnelle et morphisme inverse :
• Soit h : Σ∗ → Γ∗ un morphisme. Si L ⊆ Σ∗ est reconnaissable, alors
h(L) = {h(w) | w ∈ L} l’est aussi. Si K ⊆ Γ∗ est reconnaissable, alors
h −1 (K ) = {w ∈ Σ∗ | h(w) ∈ K } l’est aussi.
• Une substitution f : Σ → P(Γ∗ ) associe à chaque lettre de Σ un langage
f (a) ⊆ Γ∗ . On l’étend en un morphisme f : Σ∗ → P(Γ∗ ) défini par f () = {},
f (ua) = f (u)f (a) (u ∈ Σ∗ , a ∈ Σ). Pour L ⊆ Σ∗ on note
f (L) = {f (w) | w ∈ L}. La substitution est rationnelle, si f (a) ∈ Rec(Γ∗ ) pour
tout a ∈ Σ.
Si L ⊆ Σ∗ est reconnaissable, alors f (L) l’est aussi.
13/14
Sans-étoile
Expressions sans-étoile (angl. star-free)
L’ensemble SF(Σ∗ ) des expressions sans-étoile sur Σ est défini par :
• ∅ et a (a ∈ Σ) appartiennent à SF(Σ∗ )
• Si E et F sont dans SF(Σ∗ ), alors (E + F ), (E · F ) et E c aussi.
Exemples : Σ∗ = ∅c , (ab)∗ , {w ∈ {a, b}∗ | aab n’est pas facteur de w}
FOL
La logique du premier ordre FOL (angl. first-order logic) est le fragment de
MSOL qui n’utilise que des variables de premier ordre (Var2 = ∅). On note par
FOL(Σ∗ ) l’ensemble des langages décrits par des formules de FOL.
Théorème (McNaughton/Papert)
SF(Σ∗ ) = FOL(Σ∗ ), pour tout alphabet Σ.
14/14
