Calculabilité - Décidabilité (LI347) [0.3cm] Cours no7
16
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
16
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Calculabilité - Décidabilité (LI347)oCours n 7Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚7) 1 / 32Résumé du cours précédentAutomate à pile : un automate à pile est un automate fininon-déterministe couplé à une pile qui peut stocker des mots delongueur arbitraire. Le pile ne peut être lue et modifiée qu’au sommentMouvement d’un automate à pile : un AP choisit ses mouvements enfonction de l’état courant, du symbole lu et du symbole en sommet depile. On peut modifier le sommet de pileAcceptation par un automate à pile : Il y a 2 méthodes d’acceptationpour un AP : l’une en entrant dans un état final, l’autre quand la pileest vide. Ces 2 méthodes sont équivalentes dans le sens ou un langageaccepté par l’une est aussi accepté (par un autre AP) par l’autre.Configuration : On décrit les états successifs d’un AP par uneconfiguration. Il s’agit d’un triplet : état, entrée restante à lire et étatde la pileS. Graillat (Univ. Paris 6) LI347 (cours n˚7) 2 / 32eeeeFrom Final State to Empty StackÉtat final→ Pile videTheorem 6.11: Let L = L(P ), for someFPDAP = (Q, Σ, Γ,δ ,q ,Z ,F ). Then∃ PDAF F 0 0Théorème 1P , such that L =N(P ).n NSi L = L(P ) pour un AP P = (Q,Σ,Γ,δ ,q ,Z ,F), il existe un AP PF F F 0 0 Ntel que L = N(P ).NProof: LetContruction de P :NP = (Q∪{p ,p}, Σ, Γ∪{X },δ ,p ,X )N 0 0 N 0 0P = (Q∪{p ,p},Σ,Γ∪{X },δ ,p ,X ,{})N 0 0 F 0 0where δ (p , ,X ) ={(q ,Z X )}, δ (p, ,Y )N 0 0 0 0 0 Noù δ ...
Voir
Publié par
Langue
Français
Calculabilité - Décidabilité (LI347) Cours n o 7
S. Graillat (Univ. Paris 6)
Stef Graillat
Université Pierre et Marie Curie (Paris 6)
LI347 (cours n˚7)
Résumé du cours précédent
.S
1 / 32
Automate à pile : un automate à pile est un automate fini non-déterministe couplé à une pile qui peut stocker des mots de longueur arbitraire. Le pile ne peut être lue et modifiée qu’au somment Mouvement d’un automate à pile : un AP choisit ses mouvements en fonction de l’état courant, du symbole lu et du symbole en sommet de pile. On peut modifier le sommet de pile Acceptation par un automate à pile : Il y a 2 méthodes d’acceptation pour un AP : l’une en entrant dans un état final , l’autre quand la pile est vide . Ces 2 méthodes sont équivalentes dans le sens ou un langage accepté par l’une est aussi accepté (par un autre AP) par l’autre. Configuration : On décrit les états successifs d’un AP par une configuration. Il s’agit d’un triplet : état , entrée restante à lire et état de la pile
Graillat(Univ.Paris)6LI347c(uosrn˚7)2/32
État final → Pile vide Théorème 1 Si L = L ( P F ) pour un AP P F = ( Q , Σ , Γ , δ F , q 0 , Z 0 , F ) , il existe un AP P N tel que L = N ( P N ) . Contruction de P N : P N = ( Q ∪ { p 0 , p } , Σ , Γ ∪ { X 0 } , δ F , p 0 , X 0 , {} ) où δ N est ainsi définie : δ N ( p 0 , ε, X 0 ) = { ( q 0 , Z 0 X 0 ) } . Pour tout q ∈ Q , a ∈ Σ et Y ∈ Γ , δ N ( q , a , Y ) contient δ F ( q , a , Y ) . Pour tout q dans F , Y ∈ Γ ∪ { X 0 } , δ N ( q , ε, Y ) contient ( p , ε ) . Pour tout Y ∈ Γ ∪ { X 0 } , δ N ( p , ε, Y ) = { ( p , ε ) } .
S. Graillat (Univ. Paris 6)
LI347 (cours n˚7)
Équivalence entre automates à piles et langages hors-contexte
Équivalence des trois classes de langage : Les langages hors-contexte Les langages acceptés par état final Les langages acceptés par pile vide
S.Graillat(Univ.aPirs6)IL347c(uorsn˚7)
3 / 32
4/32
Des grammaires aux AP
Idée : construire un AP qui simule ⇒ ∗ g . Une forme syntaxique gauche s’écrit sous la forme xA α où A est la variable la plus à gauche. Si A → β alors xA α ⇒ g x βα . D’un point de vue de l’AP, cela va correspondre à avoir lu x et à avoir A α dans la pile : en lisant ε , l’AP va dépiler A et empiler β . Plus formellement, si w = xy alors ( q , y , A α ) ` ( q , y , βα ) Dans la configuration ( q , y , βα ) , l’AP se comporte comme précédement sauf s’il y a des terminaux dans les préfixes de β . Dans ce cas, on les dépile s’ils correspondent au symboles lus en entrée.
S. Graillat (Univ. Paris 6) LI347 (cours n˚7)
Des grammaires aux AP (suite)
Théorème 2 Soit G = ( V , T , Q , S ) une grammaire hors-contexte. Soit P = ( { q } , T , V ∪ T , δ, q , S ) un AP avec δ définie par Pour toute variable A δ ( q , ε, A ) = { ( q , β ) | A → β est une production de G } Pour tout symbole terminal a, δ ( q , a , a ) = { ( q , ε ) } Alors, P reconnait L ( G ) par pile vide. Exemple : soit la grammaire I → a | b | Ia | Ib | I 0 | I 1 E → I | E ∗ E | E + E | ( E )
.SrGaillatU(niv.Paris6)LI347(coursn˚7)
5 / 32
6/23
Des grammaires aux AP (suite)
Exemple : soit la grammaire I → a | b | Ia | Ib | I 0 | I 1 E → I | E ∗ E | E + E | ( E ) Les terminaux de l’AP sont { a , b , 0 , 1 , ( , ) , + , ∗} et a) δ ( q , ε, I ) = { ( q , a ) , ( q , b ) , ( q , Ia ) , ( q , Ib ) , ( q , I 0 ) , ( q , I 1 ) } b) δ ( q , ε, E ) = { ( q , I ) , ( q , E + E ) , ( q , E ∗ E ) , ( q , ( E )) } c) δ ( q , a , a ) = { ( q , ε ) } ; δ ( q , b , b ) = { ( q , ε ) } ; δ ( q , 0 , 0 ) = { ( q , ε ) } ; δ ( q , 1 , 1 ) = { ( q , ε ) } ; δ ( q , ( , () = { ( q , ε ) } ; δ ( q , ) , )) = { ( q , ε ) } ; δ ( q , + , +) = { ( q , ε ) } ; δ ( q , ∗ , ∗ ) = { ( q , ε ) }
S. Graillat (Univ. Paris 6)
Des AP aux grammaires
LI347 (cours n˚7)
7 / 32
Soit P = ( Q , Σ , Γ , δ, q 0 , Z 0 ) un AP. Il existe une grammaire G telle que L ( G ) = N ( P ) . G = ( V , Σ , R , S ) où l’ensemble V de variables est consitué de : Le symbole spécial S de départ. Tous les symboles de la forme [ pXq ] où p et q sont des états de Q et X est un symbole de la pile. Les productions de G sont ainsi définies : Pour tous les états p de P , G est doté de la production S → [ q 0 Z 0 p ] Si δ ( q , a , X ) contient la paire ( r , Y 1 ∙ ∙ ∙ Y k ) (il est possible que k = 0). Alors pour toute liste d’états r 1 , . . . , r k , G contient la production [ qXr k ] → a [ rY 1 r 1 ][ r 1 Y 2 r 2 ] ∙ ∙ ∙ [ r k − 1 Y k r k ]
.SrGaillat(Univ.Paris6)LI347(coursn˚7)8/23
la règle S → [ q 0 Z 0 p ] dit que les mots de S sont ceux qui permettent de passer de q 0 à un état p en dépilant Z 0 (il s’agit donc des mots reconnus par pile vide par l’automate) si ( r , Y 1 ∙ ∙ ∙ Y k ) ∈ δ ( q , a , X ) alors la règle [ qXr k ] → a [ rY 1 r 1 ][ r 1 Y 2 r 2 ] ∙ ∙ ∙ [ r k − 1 Y k r k ] dit que les mots permettant de passer de q à r k en dépilant X sont les concaténations de a , de ceux permettant de passer de r à r 1 en dépilant Y 1 , de ceux permettant de passer de r 1 à r 2 en dépilant Y 2 , etc. S. Graillat (Univ. Paris 6) LI347 (cours n˚7)
coursn˚7
9 / 32
Des AP aux grammaires (suite) Intuition : la variable [ pXq ] répresente l’ensemble des mots qui permettent de passer de l’état p à q en ayant pour effet de dépiler X De manière plus rigoureuse, on peut montrer que [ pXq ] ⇒ ∗ w si et seulement si ( p , w , X ) ` ∗ ( q , ε, ε )
q
Convertissons l’AP P N = ( { q } , { i , e } , { Z } , δ N , q , Z ) e , Z /ε i , Z / ZZ
avec V = { [ qZq ] , S } et R = { S → [ qZq ] , [ qZq ] → i [ qZq ][ qZq ] , [ qZq ] → e }
avec δ N ( q , i , Z ) = { ( q , ZZ ) } et δ N ( q , i , Z ) = { ( q , ε ) } en une grammaire G = ( V , { i , e } , R , S )
Des AP aux grammaires (suite)
lailUnt(Sra.GIL)6(743P.visira
Automates à pile déterministes
Un AP P = ( Q , Σ , Γ , δ, q 0 , Z 0 , F ) est déterministe si 1 δ ( q , a , X ) contient au plus un seul couple pour tout q ∈ Q , a ∈ Σ ∪ { ε } et X ∈ Γ . 2 Si δ ( q , a , X ) est non vide, alors δ ( q , ε, X ) est vide. Exemple : définissons L wcwr = { wcw R : w ∈ { 0 , 1 } ∗ } 0 , Z 0 / 0 Z 0 1 , Z 0 / 1 Z 0 0 , 0 / 00 0 , 1 / 01 1 , 0 / 10 0 , 0 /ε 1 , 1 / 11 1 , 1 /ε
q 0 c , Z 0 / Z 0 q 1 ε, Z 0 / Z 0 q 2 c , 0 / 0 c , 1 / 1 S. Graillat (Univ. Paris 6) LI347 (cours n˚7)
Langages réguliers et APD
11 / 32
Théorème 3 Si L est un langage régulier alors il existe un APD P tel que L = L ( P ) Preuve : Puisque que A est régulier, il existe un AFD A = ( Q , Σ , δ A , q 0 , F ) tel que L = L ( A ) . On définit alors l’APD P = ( Q Σ , { Z 0 } , δ P , q 0 , Z 0 , F ) avec δ P ( q , a , Z 0 ) = { δ A ( q , a ) , Z 0 } pour tout q ∈ Q et a ∈ Σ . On montre alors par induction sur | w | que b ( q 0 , w , Z 0 ) ` ∗ ( p , ε, Z 0 ) ⇔ δ A ( q 0 , w ) = p
S.rGialltaU(in.vaPris6)LI347(coursn˚7)12
/32
LI347 (cours n 7) ˚
13 / 32
Classification
On a langages réguliers ⊂ L ( APD ) ⊂ L ( AP ) = langages hors-contexte
Il s’agit d’inclusions strictes. En effet L wcwr ∈ L ( APD ) mais n’est pas régulier L wwr est hors-contexte mais ∈ / L ( APD )
4/32
APD et pile vide
Définition 1 On dit que L ⊂ Σ ∗ est préfixe ssi ( x , y ) ∈ L 2 et ∃ w ∈ Σ ∗ tel que x = yw ⇒ x = y ( w = ε ) Autrement dit, un langage L est préfixe s’il n’existe pas deux mots distincts de L tel que l’un soit préfixe de l’autre Exemples : L wcwr est préfixe { 0 } ∗ n’est pas préfixe Théorème 4 Un langage L = N ( P ) pour un APD P ssi L est préfixe et L = L ( P 0 ) avec P 0 un APD.
S. Graillat (Univ. Paris 6)
APD et langages hors-contexte (ambiguité)
32
Théorème 5 Si L = N ( P ) où P est un APD, alors L a une grammaire non ambigue.
S. Graillat (Univ. Paris 6)
15 / 32
Théorème 6 Si L = L ( P ) où P est un APD, alors L a une grammaire non ambigue.
Simplifier les grammaires hors-contexte, forme spéciale Lemme de pompage pour les langages hors-contexte Propriétés de fermeture Propriétés de décision
LI347(cours˚7) n
Propriétés des langages hors-contexte
(743ruoc7˚ns/61)t(Univ.Paris6)LISG.arlial
Formes normales et grammaires hors-contexte
Forme normale de Chomsky Objectif : Prouver que toute grammaire peut s’écrire de manière telle que chaque production s’écrit A → BC ou A → a où A , B et C sont des variables et a est un symbole terminal.
Noam Chomsky (1928–), professeur émérite de linguistique au MIT
Simplifications préliminaires : éliminer les symboles inutiles (n’apparaissant dans aucune dérivation d’un mot obtenu à partir du symbole de départ) éliminer les ε -productions ( A → ε ) éliminer les productions unitaires A → B , A et B étant des variables S. Graillat (Univ. Paris 6) LI347 (cours n˚7) 17 / 32
Élimination de symboles inutiles
Définition 2 Soit G = ( V , T , P , S ) une grammaire. Un symbole X est utile s’il existe une dérivation de la forme S ⇒ ∗ α X β ⇒ ∗ w avec w ∈ T ∗ . Autrement, il est dit inutile Un symbole X est productif si X ⇒ ∗ w , avec w ∈ T ∗ Un symbole X est accessible s’il existe une dérivation S ⇒ ∗ α X β avec α, β ∈ ( V ∪ T ) ∗ Marche à suivre pour éliminer les symboles inutiles : D’abord éliminer les symbole improductifs. Puis éliminer les symboles inaccessibles
On obtient une grammaire définissant L ( G ) sans symbole inutile
S. Graillat (Univ. Paris 6) LI347 (cours n˚7)
18 / 32
Élimination de symboles inutiles (exemple)
Soit la grammaire hors-contexte G définie par
S → AB | a , A → b
Les symboles S et A sont productifs, mais B n’est pas productif. Si on élimine B , on doit éliminer la régle S → AB . La grammaire devient
S → a , A → b
Seul S est accessible. En éliminant A et b , la grammaire devient S → a
Attention à l’ordre : si o ’intéresse d’abord à l’accessibilité, on trouve que n s tous les symboles sont accessibles. On élimine ensuite B qui n’est pas productif. La grammaire contient encore A et b qui sont pourtant inutiles
S. Graillat (Univ. Paris 6) LI347 (cours n˚7)
Calcul des symboles productifs
19 / 32
Soit G = ( V , T , P , S ) une grammaire. Les symboles productifs g ( G ) peuvent se calculer de la manière suivante Base : T ⊂ g ( G ) Induction : Supposons qu’il existe une production A → α et chaque symbole de α appartient à g ( G ) , alors A ∈ g ( G )
Exemple : soit G défini par S → AB | a , A → b D’abord g ( G ) = { a , b } . Puisque S → a , S est dans g ( G ) et comme comme A → b , A est aussi dans g ( G ) Au final, g ( G ) = { a , b , A , S }
S. Graillat (Univ. Paris 6) LI347 (cours n˚7)
20 / 32
Définition 3 Soit G = ( V , T , P , S ) une grammaire. Une variable X est annulable si X ⇒ ∗ ε .
Éliminer les ε -productions
Exemple : soit la grammaire
Calcul des variables annulables Base : Si A → ε alors A est annulable Induction : S’il existe une production, B → C 1 C 2 ∙ ∙ ∙ C k où chaque C i est annulable alors B est annulable
Exemple : soit G défini par S → AB | a , A → b D’abord, r ( G ) = { S } La première règle nous dit que A , B , a ∈ r ( G ) La seconde règle nous dit que b ∈ r ( G ) Au final, r ( G ) = { S , A , B , a , b }
21 / 32
S. Graillat (Univ. Paris 6) LI347 (cours n˚7)
Soit G = ( V , T , P , S ) une grammaire. Les symboles accessibles r ( G ) peuvent se calculer de la manière suivante Base : S ∈ r ( G ) Induction : Supposons que A ∈ r ( G ) et que l on ait la règle A → α . ’ Alors tout symbole de α est dans r ( G ) .
2/)2
Calcul des symboles accessibles
32ε|AAa→ABAε|BBb→B→AS
