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

De
Publié par

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ù δ ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 34
Nombre de pages : 16
Voir plus Voir moins
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 , {} ) δ 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 α 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 ] 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
)10/32
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
ilra.GSnUvial(tsi)6P.ra7(coLI34˚7)1ursn
LI347 (cours n 7) ˚
13 / 32
Classication
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 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
elbalunnatnosBteulnniassaustSes.G.arASBacSrbaelarisiv.Pt(Unillaruoc7˚nsIL)6(743
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ε|AAaABAε|BBbBAS
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.