Calculabilité - Décidabilité (LI347) [0.3cm] Cours no4

Stef Graillat

Informations

• Publié par: Omka
• Nombre de lectures: 44
• Langue: English

Extrait

Calculabilité - Décidabilité (LI347)
oCours n 4
Stef Graillat
Université Pierre et Marie Curie (Paris 6)
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 1 / 26
Résumé du cours précédent
Equivalence entre expressions régulières et automates finis : on peut
convertir un AFN en ER. On peut aussi convertir une ER en un ε-AFN.
Loi algèbrique sur les expressions régulières : permet de simplifier des
expressions
Le lemme de pompage : permet de prouver qu’un langage n’est pas
régulier
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 2 / 26Propriétés de fermeture
Enoncés du type : si certains langages sont réguliers et un langage L est
obtenu via certaines opérations sur ces langages réguliers, alors L est
régulier.
Opérations de nature ensembliste
Concaténation, renversement, fermeture
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 3 / 26
Propriétés de fermeture (suite)
Soit L et M deux langages réguliers. Alors les langages suivants sont
réguliers :
Union : L∪M
Intersection : L∩M
Complémentaire : L
Diffèrence : L\M
R RRenversement : L ={w : w ∈ L}
∗Fermeture : L
Concaténation : LM
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 4 / 26Union, concatenation et fermeture
Théorème 1
Soit L et M deux langages réguliers. Alors L∪M est régulier.
Preuve : Soit L= L(E) et M = L(F) avec E et F des ER. On a alors
L∪M = L(E)∪L(F) = L(E +F) par définition.
Théorème 2
Soit L et M deux langages réguliers. Alors LM est régulier.
Preuve : Soit L= L(E) et M = L(F) avec E et F des ER. On a alors
LM = L(E).L(F) = L(EF) par définition.
Théorème 3
∗Soit L un langage régulier. Alors L est régulier.
∗ ∗ ∗Preuve : Soit L= L(E) avec E une ER. On a alors L = L(E) = L(E )
par définition.
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 5 / 26
Complémentaire, intersection et différence
Théorème 4
?Soit L un langage régulier. Alors le complémentaire de L dans Σ noté L
est régulier.
Preuve : Convertir l’expression régulière en un ε-AFN, puis convertir cet
ε-AFN en un AFD A = (Q,Σ,δ,q ,F). Soit alors l’automate0
B = (Q,Σ,δ,q ,Q\F). On a L= L(B). 0
∗Exemple : complémentaire du langage L= (0+1) 01
L L
00
1 1
0 0
0 0
{q } {q ,q } {q ,q } {q } {q ,q } {q ,q }0 0 1 0 2 0 0 1 0 2
1 1
1 1
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 6 / 26Intersection et différence
Théorème 5
Soit L et M deux langages réguliers. Alors L∩M est régulier.
Preuve : Par les lois de De Morgan, on a L∩M = L∪M. Par conséquent,
L∩M est régulier comme complémentaire et l’union de langages régulier.
Corollaire 1
Soit L et M deux langages réguliers. Alors L\M est régulier.
Preuve : Comme L\M = L∩M, on en déduit que L\M est régulier.
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 7 / 26
Retour sur l’intersection
Théorème 6
Soit L et M deux langages réguliers. Alors L∩M est régulier.
Preuve : Soit A = (Q ,Σ,δ ,q ,F ) et B = (Q ,Σ,δ ,q ,F ) deuxL L L L L L M M M M
automates déterministes reconnaissant respectivement L et M.
→ on va construire un automate qui simule A et A en parallèle et quiL M
accepte si et seulement si A et A acceptent.L M
Posons A = (Q ×Q ,Σ,δ ,(q ,q ),F ×F ) avecL∩M L M L∩M L M L M
δ ((p,q),a) =(δ (p,a),δ (q,a))L∩M L M
⇒ A reconnait le langage L∩M. L∩M
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 8 / 26Retour sur l’intersection (exemple)
0,10,1 01
10p q r s
1
1
pr ps
0 0
1qr qs 0,10
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 9 / 26
Renversement
Renversement : a a ···a a → a a ···a a1 2 n−1 n n n−1 2 1
RPour un mot w, on note w son miroir
R RÉtant donné un langage L, on note L ={w : w ∈ L}
Théorème 7
RSoit L un langage régulier. Alors L est régulier.
Preuve 1 : Si L est régulier, il existe un AFD A qui le reconnait :
Renverser toutes les flèches dans le diagramme de transition de A
L’état de départ de A devient seul et unique état acceptant.
Créer un nouvel état p de départ avec ε-transitions sur chaque état0
acceptant de A.
RL’automate ainsi construit reconnait L .
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 10 / 26Renversement (suite)
Théorème 8
RSoit L un langage régulier. Alors L est régulier.
RPreuve 2 : Si L= L(E) avec E une ER, on va construire un ER E telle
R Rque L(E ) = L(E) par induction structurelle
RBase : Si E est égale à ε, ∅ ou a alors E = E
Induction :
R R Rsi E = F +G alors E = F +G
R R Rsi E = F.G alors E = G .F
∗ R R ∗si E = F alors E = (F )
R R ROn vérifie que E ainsi construit satisfait L(E ) =(L(E)) .
∗ R ∗Exemple : si L= (0+1)0 alors L = 0 (0+1)
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 11 / 26
Propriétés de décision des langages réguliers
Représentation finie des langages réguliers :
AFD
AFN, ε-AFN
Expressions régulières
Questions :
Le langage décrit est-il vide?
Un mot donné appartient-il au langage décrit?
Deux descriptions différentes définissent-elles le même langage?
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 12 / 26Conversion entre représentations
On en a déjà vu quelques-unes... mais combien coutent-elles?
Des AFN aux AFD :
On part d’un ε-AFN à n états :
3Calcul des ε-fermetures : O(n )
nConstruction des sous-ensembles : il y en a 2 mais il faut aussi
2obtenir le diagramme de transition! Chaque transition coute O(n ).
3 nCout global : O(n 2 )
Des AFD aux AFN :
C’est le plus simple et ça ne coute que O(n) opérations.
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 13 / 26
Conversion entre représentations (suite)
Des automates aux expressions régulières :
À chaque étape, la longueur de l’expression peut quadrupler et il y a n
étapes!
3 3 nÉcrire les n expressions coute O(n 4 ).
L’élimination d’états ne change pas la complexité (juste la constante).
Si l’entrée est un ε-AFN à n états, le coute de cette conversion est
n3 2O(n 4 )!
Des expressions régulières aux automates :
Conversion vers les ε-AFN linéaire en la longueur de l’expression.
3Pour passer à un AFN : O(n )
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 14 / 26Tester si un langage régulier est vide
Représentation : un automate fini.
Reformulation de la question : existe-t-il un moyen de joindre un état
acceptant à partir de l’état de départ (parcours de graphe)?
Par induction :
Base : L’état de départ est atteignable par l’état de départ.
Induction : Si l’état q est atteignable par l’état de départ, tout état
atteignable depuis q est atteignable par l’état de départ.
2Coût total : O(n ).
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 15 / 26
Tester si un langage régulier est vide (suite)
On peut aussi étudier une ER E et dire si L(E) =∅.
On procède de manière récursive :
E = F +G. Alors L(E) est vide ssi L(F) et L(G) sont vides
E = F.G. Alors L(E) est vide ssi L(F) ou L(G) sont vides
∗E = F . Alors L(E) n’est jamais vide puisque ε∈ L(E)
E = ε. Alors L(E) est non vide
E = a. Alors L(E) est non vide
E =∅. Alors L(E) est vide
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 16 / 26Tester l’appartenance à un langage régulier
Pour tester si w ∈ L(A) avec A un AFD, on en simule le
fonctionnement. Si |w| = n alors cela coute O(n).
2Si A est un AFN à s états, simuler A sur w coute O(ns ).
Si A est un un ε-AFN à s états (il faut alors calculer les ε-fermetures),
3simuler A sur w coute O(ns ).
Si L= L(E) pour une ER E de longueur s, on convertit E en un
3ε-AFN avec 2s états. Simuler w sur cette machine coute O(ns ).
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 17 / 26
Équivalence et minimisation d’automates
Tester si deux langages réguliers définissent le même langage.
Conséquence : Minimisation d’un AFD en un AFD unique.
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 18 / 26Tester l’équivalence de deux états d’un AFD
Définition 1
Soit A = (Q,Σ,δ,q ,F) un AFD et p,q ∈ Q. On dit que p et q sont0
?équivalents et on note p≡ q si pour w ∈Σ ,
b bδ(p,w) est un état acceptant ssi δ(q,w) est un état acceptant.
Si p≡/ q, on dit que p et q sont distinguables.
∗Autrement dit, p≡/ q ssi il existe w ∈Σ tel que
b bδ(p,w)∈ F et δ(q,w)∈/ F
ou
b bδ(p,w)∈/ F et δ(q,w)∈ F
S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 19 / 26
Tester l’équivalence de deux états d’un AFD
Exemple :What about A and E?
1
0
0 1 0
A B C D
1
1 0
0
1
1 1 0
E F G H
1 0
0
b bˆ ˆδ(C,ε)∈ F, δ(G,ε)∈/ F ⇒ C≡/ Gδ(A,) =A∈/ F,δ(E,) =E∈/ F
b bˆ ˆδ(A,01)δ=(A,C1)∈ F=, δ