Langages réguliers et automates finis
Université Libre de Bruxelles 2008 - 2009
Denis BOIGELOT Sébastien COLLETTE Gilles GEERAERTS
Coordonnées
• Denis Boigelot • [email protected] • 2N8.211 • http://www.ulb.ac.be/di/ssd/tmassart/Compil • http://student.ulb.ac.be/~dboigelo/
Langage régulier
Langage régulier
Soit un alphabet ! (fini)
Cas de base: • Ø est un langage régulier • {"} est un langage régulier • !a " !, {a} est un langage régulier
Soient L et K des langages réguliers
Inductions: • L#K := { l#k | l " L # k " K} est régulier • L $ K est régulier • L* := {"} $ {www…w | w " L} est
régulier
Automate fini
Propriété importante
M = !Q, !, $, q0, F" où • Q est un ensemble fini des états; • ! est l’alphabet des symboles à l’entrée; • $ est la relation de transition: Q % ! % Q; • q0 est l’état initial; • F % Q ensemble des états accepteurs.
Si R est un langage régulier, alors il existe un automate fini M tel que L(M) = R.
Exercice 1
Solution 1.1
Démontrez, à l’aide de la définition inductive des langages réguliers, que les deux langages suivants sont réguliers (l’alphabet considéré est ! = {0, 1}):
1. L’ensemble des mots composés d’un nombre
arbitraire de 1, suivis de 01, suivis d’un nombre arbitraire de 0.
2. L’ensemble des nombres binaires impairs.
• 1 " ! et 0 " !. Donc {1} et {0} sont des langages
réguliers.
• La fermeture de Kleene d’un langage régulier est un langage régulier. Donc {1}* et {0}* sont des langages réguliers.
• La concaténation de langages réguliers est un
langage régulier. Donc {1}* # {0} # {1} # {0}* est un langage régulier.
Solution 1.2
Exercice 2
Remarque: un nombre binaire impair se termine nécessairement par 1.
• {1} et {0} sont des langages réguliers. • {1} $ {0} est régulier. • ({1} $ {0})* est régulier. • ({1} $ {0})* # {1} est régulier.
1. Démontrez que tout langage fini est régulier.
2. Le langage L = {0n1n | n = 0, 1, 2, …} est-il
régulier ? Expliquez.
Solution 2.1
Solution 2.2
• Soit L = {w1, w2, …, wn} un langage fini. • Comme chaque mot wi est une concaténation finie de caractères de !, il est clair que {wi} est régulier pour tout 1 & i & n.
• Donc, {w1} $ {w2} $ … $ {wn} = L est
régulier.
Réponse: Non!
• Preuve par contradiction. Supposons que L est
régulier.
• Donc, il existe un automate fini A = !Q, !, $, q0, F". • Intuitivement: comme Q est fini, il existe un mot de L qui est accepté en passant deux fois par le même état q. Par exemple: w = 02|Q|12|Q|.
Solution 2.2
• Donc, il existe un chemin de q à q labellé par 0k1, une boucle allant de q à q labellée par 0k2 et un chemin allant de q à q' " F, labellé par par 0k312|Q|, avec k1 + k2 + k3 = 2|Q|.
0
• Mais alors, on peut aussi accepter, par exemple le
mot 0k10k312|Q|, qui n’est pas dans L.
• Contradiction: A ne peut pas exister et donc L n’est
pas régulier.
Automate fini
• DFA (deterministic finite automata)
a a
1
• NFA (nondeterministic finite automata)
a a
1
• "-NFA (epsilon-transitions NFA)
!
1
Exercice 3
Solution 3.1
Donnez un automate non déterministe qui accepte chacun des langages suivants (définis sur l’alphabet ! = {0, 1}):
1. Toutes les chaînes qui se terminent par 00.
2. Toutes les chaînes dont le 10ème symbole, compté à
partir de la fin de la chaîne, est un 1.
3. Ensemble de toutes les chaînes dans lesquelles chaque
paire de 0 apparaît devant une paire de 1.
4. Ensemble de toutes les chaînes ne contenant pas 101.
5. Tous les nombres binaires divisibles par 4.
0,1
1
0
0
2
3
Solution 3.2
Solution 3.3
0,1
1
1
0,1
3
12
0,1
11
0,1
10
0,1
4
9
0,1
Publicité
0,1
5
8
0,1
6
0,1
0,1
7
0
1
1
0
1
0
0,1
Err
1
0
Solution 3.4
Solution 3.5
0
1
1
0
0
1
0,1
Err
0,1
0
0
0,1
0
Liens entre automates
"-NFA
NFA
séance 1 exo 4
séance 2 exo 3
Trivial
RE
séance 2 exo 2
DFA
Déterminiser un automate
Technique: subset construction
NFA N = !QN, !, $N, q0, FN" ( DFA D = !QD, !, $D, {q0}, FD" où • QD = !(QN) • FD = {S | S % QN tel que S ) FN * Ø} • ! S % QN, !a " !, $D(S,a) = $ $N(p,a)
p " S
Supprimer les !-transitions
"-NFA E = !Q, !, $E, q0, F" ( NFA N = !Q, !, $N, q0, F" tel que:
soit + " !, si q’ " $E(q, +), alors (q, +, q’) " $N
^
c’est-à-dire: s’il existe un chemin de q à q’ passant par un et un seul + (plus éventuellement des ") dans le "-NFA, alors on inclut la transition (q, +, q’) au NFA
Exercice 4.1
Déterminisez:
0,1
p
0
0
r
q
0
0
1
1
t
s
0
Exercice 4.2
Exercice 4.3
Déterminisez:
Déterminisez:
p
01
s
0,1
1
0
q
1
1,0
r
Solution 4.1
"
( {p}
{p,q}
* {p,t}
* {p,q,r,s}
* {p,s}
1
{p}
{p,t}
{p,s}
{p,t}
Publicité
{p}
0
{p,q}
{p,q,r,s}
{p,q}
{p,q,r,s}
{p,q}
a
q
b
!
b
!
a
p
c
c
a
r
Solution 4.1
1
p
1
0
p,q
0
0
0
1
p,s
p,t
1
1
p,q,r,s
0
Solution 4.2
" ( {p} * {q} {r} * {s} * {q,s} * {q,r} * {r,s} * {p,q,r} * {q,r,s} Ø
1 {q} {q,r} {p} {p} {p,q,r} {p,q,r} {p} {p,q,r} {p,q,r} Ø
0 {q,s} {r} {s} Ø {r} {r,s} {s} {q,r,s} {r,s} Ø
Solution 4.3
Suppression des "-transitions:
a
{p}
b
c
{p,q}
{p,q,r}
{p,q}
{p,q,r}
{p,q,r}
{p,q,r}
{p,q,r}
{p,q,r}
p
q
r
Solution 4.2
1
0
1
1
0
1
0
1
q
1
q,r
0
1
p
0
q,s
1
p,q,r
1
s
0
Ø
1,0
0
0
r
r,s
0
q,r,s
Solution 4.3
a,b,c p
b,c a,b,c
a,b,c
c
a,b,c
Publicité
q
a b c
b c
r
a,b,c
Solution 4.3
"
( {p}
a
{p}
b
c
{p,q}
{p,q,r}
{p,q}
{p,q}
{p,q,r}
{p,q,r}
* {p,q,r}
{p,q,r}
{p,q,r}
{p,q,r}
Solution 4.3
a,b
p,q
a
p
b
c
c
a,b,c
p,q,r
Exercice 5
Écrivez une fonction C qui implémente cet automate et renvoie le numéro d’état accepteur.
H
4
I
5
6
L
E
7
1
W
8
!\{H}
!\{W,I}
I
!\{F}
!\{I}
!\{L}
!\{E}
!
3
!
!
F
9
2
!={A,B,C,...,Z}
Solution 5
char buffer ; // Initialise au 1er car de l’input
char next_char()
{return buffer;}
void read_next()
{buffer = getchar();}
bool alpha(char c)
{return (c >= ’A’ && c <= ’Z’);}
Solution 5
Solution 5
int automate() {
int state = 8;
char c;
while (true) {
switch state {
case 8:
if (next_char() == ’W’) state = 4;
else if (next_char() == ’I’) state = 9;
else if (alpha(c)) state = 3;
else state = 8;
read_next();
break;
case 4:
...
case 2:
if (alpha(c)) state = 3;
else return 2; // Pas de read_next!
read_next();
break;
}
}