BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Langages formels - Cours 1, 2, 3
Francois Schwarzentruber
ENS Rennes, France
2015
1 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Recherche de fichiers
Je veux les
fichiers dont
le nom est
dans le
langage desmots quicontiennentun a
Recherche de fichiers
arosoir.txtboite.txtmiaou.txtidees.txt
2 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee clef du coursProbleme : un langage peut etre infini{miaou, arosoir , avec , piano, contrebasse, . . . }Solution : utiliser des representations finis
Example (expression rationnelle)donne la morphologie des mots du langage
(a + b + . . . z)∗a(a + b + . . . z)∗
Example (formule de la logique monadique du second ordre)proche de la langue naturelle
mot qui contient un a↓
il existe une position dans le mot ou il y a un a↓
∃x , a(x)
3 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
D’autres representations
Automates (cours 1 ou 2)
q0
startstart q1
q2 a
ba
a
Grammaires (cours 5?)
S → (S + S)S → (S × S)S → un nombre
(surprise, cours 6?)
4 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Enjeu 1 : des algorithmes pour differents problemes
Descriptionfini
un mot
appartient? oui/non
Descriptionfini
langage vide? oui/non
Descriptionfini
langage fini? oui/non
...
5 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Enjeu 2 : expressivite
Existe-t-il un langage que l’on peut decrire
avec
une expression rationnelleun automateune formule de MSOune grammaire. . .
mais pas avec
une expression rationnelleun automateune formule de MSOune grammaire. . .
?
6 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Enjeu 3 : concision
Existe-t-il un langage que l’on peut decrire
plus succinctement avec
une expression rationnelleun automateune formule de MSOune grammaire. . .
qu’avec
une expression rationnelleun automateune formule de MSOune grammaire. . .
?
7 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotsLangages
Outline
1 BasesMotsLangages
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministe
5 Automate minimal
8 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotsLangages
Outline
1 BasesMotsLangages
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministe
5 Automate minimal
9 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotsLangages
L’ensemble des mots est un monoıde
10 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotsLangages
Exemple de morphisme de monoıdes
11 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotsLangages
Outline
1 BasesMotsLangages
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministe
5 Automate minimal
12 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotsLangages
Langage
13 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Expressions rationnellesLogique monadique du second ordre
Outline
1 Bases
2 Expressions rationnelles et MSOExpressions rationnellesLogique monadique du second ordre
3 Automates finis
4 Automate deterministe
5 Automate minimal
14 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Expressions rationnellesLogique monadique du second ordre
Outline
1 Bases
2 Expressions rationnelles et MSOExpressions rationnellesLogique monadique du second ordre
3 Automates finis
4 Automate deterministe
5 Automate minimal
15 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Expressions rationnellesLogique monadique du second ordre
Syntaxe/semantique
Syntaxe
(ce que l’on ecrit dans un logiciel pour
representer un langage)
Semantique
(ce que l’on veut representer)
a∗b
(a ∪ b)
(a ∪ b)∗
(b ∪ a)∗
{anb | n ∈ N}
{a, b}
{a, b}∗
{anbn | n ∈ N}
16 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Expressions rationnellesLogique monadique du second ordre
Outline
1 Bases
2 Expressions rationnelles et MSOExpressions rationnellesLogique monadique du second ordre
3 Automates finis
4 Automate deterministe
5 Automate minimal
17 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Expressions rationnellesLogique monadique du second ordre
Syntaxe/semantique
Syntaxe
(ce que l’on ecrit dans un logiciel pour
representer un langage)
Semantique
(ce que l’on veut representer)
∃x, a(x)
∀x, a(x)
{w1 . . .wn | n ∈ N et il existe i , wi = a}
{an | n ∈ N}
18 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finisMotivationDefinitionsTheoreme de KleeneLemme de pompage
4 Automate deterministe
5 Automate minimal19 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finisMotivationDefinitionsTheoreme de KleeneLemme de pompage
4 Automate deterministe
5 Automate minimal20 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Motivation 1 : Outil central pour l’expressivite
Meme expressivite
Automates finis
MSO Expressions rationnelles
Montrer que {anbn | n ∈ N} n’est pas rationnel
Stabilite par ∩, par complementaire
21 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Motivation 2 : Outil central pour l’algorithmique
automatefini
un mot
appartient oui/non
automatefini
langage vide? oui/non
automatefini
langage fini oui/non
...→ utiliser des algorithmes sur les graphes.
22 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Motivation 3 : abstraction d’un programme
Example (Editeur de texte)
j’ecris
startstart
selectionen cours
selectiondrag &drop
appui lettre
bouger souris
bouger souris
appuilettre,clic
boutonsourisenfonce
boutonsourisenfoncesur rien
boutonsourisrelache
boutonsouris en-fonce surselection
bouton relache
23 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Motivation 4 : automate = systeme d’equations lineaires
Example
q0
startstart q1
q2 a
ba
a
q0 = aq1 + aq2
q1 = ε+ bq1
q2 = ε+ aq2
24 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Discussion : des expressions rationnelles aux automates
On sait construire des automates pour L(∅), L(ε), L(a) :
q0
startstart
q0
startstart
q0
startstart
q1a
. . .
Comment construire un automate pour L(e1 ∪ e2) ?a partir d’automates de L(e1) et L(e2) ?
Solution : on utilise des ε-transitions.
25 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Automate non-deterministe avec ε-transitions
q0
startstart
q1 q2
q3 q4
ε
ε
a
b
26 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finisMotivationDefinitionsTheoreme de KleeneLemme de pompage
4 Automate deterministe
5 Automate minimal27 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Definition d’un automate non-deterministe avecε-transitions
1start
2 3
b εa
aa, b
28 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finisMotivationDefinitionsTheoreme de KleeneLemme de pompage
4 Automate deterministe
5 Automate minimal29 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Des expressions rationnelles aux automates ?
Comment a partir d’automates pour L(e1), L(e2)
Ae1
start
Ae2
start
on construit des automates pour L(e1 + e2), L(e1; e2) et L(e∗1 ) ?
30 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Des automates aux expressions rationnelles ?
automatenon-deterministea 3 etats
automategeneralise a5 etats
automategeneralise a4 etats
automategeneralise a3 etats
automategeneralise a2 etats
expressionrationnelle
a. b.
b.
b.c.
31 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Automate ‘hybride’ : automate generalise
32 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Suppression d’un etat
33 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finisMotivationDefinitionsTheoreme de KleeneLemme de pompage
4 Automate deterministe
5 Automate minimal34 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationDefinitionsTheoreme de KleeneLemme de pompage
Lemme de pompage
35 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministeMotivationsAutomate deterministeDeterminisation
5 Automate minimal
36 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministeMotivationsAutomate deterministeDeterminisation
5 Automate minimal
37 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Motivations
Calculer un automate qui reconnaıt le complementaire
q0
startstart q1
q2
a
a=⇒
q0
startstart q1
q2
a
a
Une execution unique pour un mot donne.
38 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministeMotivationsAutomate deterministeDeterminisation
5 Automate minimal
39 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Definition
q0
startstart q1
q2
a
b
q3
a, b
a, b a, b
40 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Definition
q0
startstart q1
q2
a
b
q3
a, b
a, b a, b
41 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Passage au complementaireA
q0
startstart q1
q2
a
b
q3
a, b
a, b a, b
A
q0
startstart q1
q2
a
b
q3
a, b
a, b a, b
42 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministeMotivationsAutomate deterministeDeterminisation
5 Automate minimal
43 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Determinisation
1start
2 3
b εa
aa, b
Je suis dans 1 ou dans 3 ;
Puis si je lis b, je suis dans 2 ;
Puis si je lis a, je suis dans 2 ou dans 3 ;
...
44 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
MotivationsAutomate deterministeDeterminisation
Bilan
Expressionrationnelle
stabilite par., ∪, ∗
MSOproche de lalangue naturelle
Automate non-deterministe avecε-transitions
stabilite par ∩ (produit)
lemme de pompage
Automate non-deterministe sansε-transitions
Automatedeterministe
stabilite parcomplementaire
( )
45 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministe
5 Automate minimalIdee generaleQuotientAutomate des residuelsAlgorithme de Moore
46 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Motivation
Application en analyse lexicale
Expressionrationnelle
Thomson etdeterminisation
automatedeterministecomplet (outous les etatssont accessibles)
Minimisation
automatedeterministeminimal
En fait... il est unique (a isomorphisme pres).
47 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Idee generale de la preuve de l’unicite
A ∼iso
automatequotientA/∼
∼iso
automatedes residuelsAL
A minimal
tous les etats de A sont ac-
cessibles depuis l’etat initial
48 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministe
5 Automate minimalIdee generaleQuotientAutomate des residuelsAlgorithme de Moore
49 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Quotient
50 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Congruence
q δ(q, a)
q′ δ(q′, a)
a
a
∼ ∼
51 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministe
5 Automate minimalIdee generaleQuotientAutomate des residuelsAlgorithme de Moore
52 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Quotient d’un automate minimal...
A ∼iso
automatequotientA/∼
∼iso
automatedes residuelsAL
A minimal
tous les etats de A sont ac-
cessibles depuis l’etat initial
53 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministe
5 Automate minimalIdee generaleQuotientAutomate des residuelsAlgorithme de Moore
54 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Residuel
Example (Palindromes, (aaba)−1L)
0010
0100101001110100110110100...
Si on est dans un automate pour L et qu’on a lu 0010, c’estl’ensemble des mots qui nous menent dans un etat final.
55 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Automate des residuels
56 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministe
5 Automate minimalIdee generaleQuotientAutomate des residuelsAlgorithme de Moore
57 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Quotient = automate des residuels
A ∼iso
automatequotientA/∼
∼iso
automatedes residuelsAL
A minimal
tous les etats de A sont ac-
cessibles depuis l’etat initial
58 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Outline
1 Bases
2 Expressions rationnelles et MSO
3 Automates finis
4 Automate deterministe
5 Automate minimalIdee generaleQuotientAutomate des residuelsAlgorithme de Moore
59 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Algorithme de Moore
Q \ F F
60 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Algorithme de Moore
61 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Algorithme de Moore
62 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Algorithme de Moore
63 / 57
BasesExpressions rationnelles et MSO
Automates finisAutomate deterministe
Automate minimal
Idee generaleQuotientAutomate des residuelsAlgorithme de Moore
Algorithme de Moore
expressionreguliere
automatenon-deterministeavec ε-transitions
automatedeterministecomplet A(ou tous lesetats sontaccessibles)
∼0 ∼1 ∼2∼3
(stabilisation)
automateminimal A∼3
expToAutdeterminisation
a.b. b. b.
c.
64 / 57