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

Stef Graillat

Informations

• Publié par: Erzo
• Nombre de lectures: 39
• Langue: Français

Extrait

Calculabilité - Décidabilité (LI347)
oCours n 6
Stef Graillat
Université Pierre et Marie Curie (Paris 6)
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 1 / 20
Résumé du cours précédent
Grammaire hors-contexte : une façon de décrire un langage par des
règles récursives. Un grammaire consiste en des variables, des
symboles terminaux, un symbole de départ et des règles de production
Dérivations et langages : le langage associé à une grammaire est
l’ensemble des mots constitués de terminaux que l’on peut dériver à
partir du symbole de départ
Dérivations droites et gauches : on remplace à chaque fois la variable
la plus à gauche (à droite)
Arbres de dérivation : un arbre de dérivation est un arbre qui capture
les informations essentielles d’une dérivation.
Ambiguité : une grammaire est dite ambigue si on peut trouver un
mot de terminaux ayant deux arbres de dérivation distincts ou bien de
manière équivalente deux dérivations grauche (ou droite) distinctes
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 2 / 20Automates à piles
Automates associés aux langages hors-contexte.
Extension des AFN à ε-transitions auxquels on ajoute une pile.
Reconnaissance des langages par états acceptants
Reconnaissance des langages par pile vide
Équivalences et langages hors-contexte
Automates à pile déterministes
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 3 / 20
Définition d’un automate à pile
Automate fini non-déterministe qu’on dote d’une pile (structure de données
classique).
Fonctionnement global :
Consommation du symbole d’entrée à chaque transition.
Aucun changement ou modification de l’état
Modification de la pile ou pas (effacement du symbole au-dessus, ou
modification de ce symbole, ou ajout d’un symbole).
Automate
Entrée Accepte / rejettefini
Pile
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 4 / 20Exemple
R ?Exemple : L ={ww | w ∈{0,1} }wwr
Une grammaire pour L est : P → 0P0, P → 1P1, P → εwwr
Un AP pour L a 3 états et opère comme suit :wwr
1 On suppose qu’on lit w. On reste à l’état 0 et on empile les symboles
R2 On suppose qu’on est au milieu de ww . On passe à l’état 1
R3 On suppose qu’on lit maintenant w . On compare alors avec le haut
de la pile. Si les symboles sont identiques, on dépile, sinon on ne fait
rien
4 Si la pile est vide, on va à l’état 2 et on accepte
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 5 / 20
Exemple (suite)
0,Z /0Z0 0
1,Z /1Z0 0
0,0/00
0,1/01
0,0/ε1,0/10
1,1/ε1,1/11
q q q0 1 2
ε,Z /Zε,Z /Z 0 00 0
ε,0/0
ε,1/1
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 6 / 20Définition formelle
Un automate à pile (AP) est un septuplet P = (Q,Σ,Γ,δ,q ,Z ,F) où0 0
Q un ensemble fini d’états
Σ un ensemble fini de symboles d’entrées
Γ un alphabet de pile (symboles pouvant être stocké dans la pile)
∗δ : Q×Σ∪{ε}×Γ→P(Q×Γ ) la fonction de transition (3
arguments) δ(q,a,X) où
q est un état
a un symbole de Σ
X un symbole de pile (dans Γ)
La sortie est un ensemble fini de pairs (p,γ) où p∈ Q et γ une chaîne
de symboles qui remplace X au haut de la pile.
q l’état de départ0
Z le symbole de départ0
F l’ensemble des états acceptants (ou états finaux)
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 7 / 20
Notation graphique
Notation similaire à celle des AFD.
Les nœuds correspondent aux états.
Une flèche indique l’état de départ et les états finaux sont entourés de
deux cercles.
Les flèches correspondent aux transitions. Un label a,X/α de l’état q
vers l’état p signifie que (p,α) est dans δ(q,a,X).
0,Z /0Z0 0
1,Z /1Z0 0
0,0/00
0,1/01
0,0/ε1,0/10
1,1/ε1,1/11
q q q0 1 2
ε,Z /Zε,Z /Z 0 00 0
ε,0/0
ε,1/1
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 8 / 20Table
0,Z /0Z0 0
1,Z /1Z0 0
0,0/00
0,1/01
0,0/ε1,0/10
1,1/ε1,1/11
q q q0 1 2
ε,Z /Zε,Z /Z 0 00 0
ε,0/0
ε,1/1
Cet AP est le septuplet P = ({q ,q ,q },{0,1},{0,1,Z },δ,q ,Z ,{q })0 1 2 0 0 0 2
avec δ donné par la table suivante
0,Z 1,Z 0,0 0,1 1,0 1,1 ε,Z ε,0 ε,10 0 0
→ q q ,0Z q ,1Z q ,00 q ,01 q ,10 q ,11 q ,Z q ,0 q ,10 0 0 0 0 0 0 0 0 1 0 1 1
q q ,ε q ,ε q ,Z1 1 1 1 0
? q2
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 9 / 20
Descriptions instantannées (configurations)
Configuration d’un AP par un triplet (q,w,γ) où
q est l’état de l’AP
w ce qui reste à lire de l’entrée
γ est le contenu de la pile.
? ?Si δ(q,a,X) contient (p,α) alors pour tout w ∈ Σ et β ∈ Γ
(q,aw,Xβ)‘ (p,w,αβ)
∗Transitions étendues : ‘
∗Base : I ‘ I pour toute configuration I
∗Induction : I ‘ J s’il existe une configuration K telle que I ‘ K et
∗K ‘ J
∗Autrement I ‘ J ssi il existe des configurations K ,K ,...,K telles que1 2 n
I = K , J = K et K ‘ K pour tout i = 1,2,...,n−11 n i i+1
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 10 / 20e
e
e
e
e
Exemple
Transitions étendues pour l’AP avec 1111 en entrée
0,Z /0Z0 0
1,Z /1Z0 0
0,0/00
0,1/01
0,0/ε1,0/10
1,1/ε1,1/11
q q q0 1 2
ε,Z /Zε,Z /Z 0 00 0
ε,0/0
ε,1/1
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 11 / 20
Exemple (suite)
Transitions étendues pour l’AP avec 1111 en entrée
( q , 1111, Z )0 0
q( q , 111, 1Z ( , 1111, Z ( , 1111, Z) q ) )20 0 0 01
0,Z /0Z0 0
1,Z /1Z0 0
( q , 11, 11Z ( , 111, 1Z ( , 11, Z) q ) q )0 0 0 00,0/00 1 1
0,1/01
0,0/ε1,0/10
1,1/ε q1,1/11 ( q , 1, 111Z ( , 11, 11Z ( , 11, Z) q ) )20 0 0 01
q q q0 1 2
ε,Z /Zε,Z /Z 0 00 0 ( q , , 1111Z ( , 1, 111Z ( , 1, 1 Z) q ) q )0 0 0 01 1
ε,0/0
ε,1/1
( q , , 1111Z ) ( q , , 11 Z ) ( q , , Z )
0 0 01 1 1
q( , , Z )2 0
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 12 / 20
188Quelques remarques
Propriété 1
On a les propriétés suivantes :
1 Si une suite de configuration est valide alors la suite obtenue en
ajouter une chaine à la fin du composant 2 est encore valide
2 Si une suite de configuration est valide alors la suite obtenue en
ajouter une chaine à la fin du composant 3 est encore valide
3 Si une suite de configuration est valide et si la fin de l’entrée n’est pas
consommée alors en la retirant, la suite de configuration est encore
valide
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 13 / 20
Quelques résultats
Proposition 1
∗Si P = (Q,Σ,Γ,δ,q ,Z ,F) est un AP et (q,x,α)‘ (p,y,β) alors pour0 0
∗ ∗toute chaîne w ∈ Σ et γ ∈ Γ on a
∗(q,xw,αγ)‘ (p,yw,βγ)
Remarque 1 : si γ = ε on obtient la propriété 1 et si w = ε, on obtient la
propriété 2
Remarque 2 : la réciproque est fausse
Pour la propriété 3, on a
Proposition 2
∗Si P = (Q,Σ,Γ,δ,q ,Z ,F) est un AP et (q,xw,α)‘ (p,yw,β) alors on0 0
a
∗
(q,x,α)‘ (p,y,β)
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 14 / 206
Langages d’un automate à pile par état final
Définition 1
Soit P = (Q,Σ,Γ,δ,q ,Z ,F) un AP. Alors le langage accepté par état0 0
final est
∗L(P) ={w : (q ,w,Z )‘ (q,ε,α),q∈ F}0 0
R ?Exemple : l’AP suivant reconnait le langage L ={ww | w ∈{0,1} }wwr
par état final
0,Z /0Z0 0
1,Z /1Z0 0
0,0/00
0,1/01
0,0/ε1,0/10
1,1/ε1,1/11
q q q0 1 2
ε,Z /Zε,Z /Z 0 00 0
ε,0/0
ε,1/1
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 15 / 20
Langages d’un automate à pile par état final (suite)
Prouver que L(P) = Lwwr
R“⊃” soit x ∈ L alors x = ww et la suite de transition est validewwr
R ∗ R R R R ∗
(q ,ww ,Z )‘ (q ,w ,w Z )‘ (q ,w ,w Z )‘ (q ,ε,Z )‘ (q ,ε,Z )0 0 0 0 1 0 1 0 2 0
“⊂” on observe que la seule façon attendre l’état q est d’être à l’état q2 1
avec Z sur la pile0
∗ R→ il suffit donc de montrer que si (q ,x,Z )‘ (q ,ε,Z ) alors x = ww0 0 1 0
pour une chaîne w. Montrons par induction sur |x| que
∗ R(q ,x,α)‘ (q ,ε,α)⇒ x = ww0 1
Base : si x = ε alors x est un palindrome
Induction : Supposons x = a a ···a avec n > 0. À partir de (q ,x,α), il1 2 n 0
y a 2 possiblités
Cas 1 : (q ,x,α)‘ (q ,x,α).0 1
∗Mais (q ,x,α)‘ (q ,ε,β) implique que |β| <|α| et donc β = α1 1
S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 16 / 20Langages d’un automate à pile par état final (suite)
Cas 2 : (q ,a a ···a ,α)‘ (q ,a ···a ,a α).0 1 2 n 0 2 n 1
On doit donc avoir
(q ,a a ···a ,α)‘ (q ,a ···a ,a α)‘···‘ (q ,a ,a α)‘ (q ,ε,α)0 1 2 n 0 2 n 1 1 n 1 1
Par conséquent, a = a et1 n
∗
(q ,a ···a ,a α)‘ (q ,a ,a α)0 2 n 1 1 n 1
Donc
∗
(q ,a ···a ,a α)‘ (q ,ε,a α)0 2 n−1 1 1 1
R RPar hypothèse de récurrence a ···a = yy et donc x = a yy a est un2 n−1 1 n
palindrome
S. Graillat (Univ. Paris 6) LI347 (cours