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

Stef Graillat

Description

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ù δ ...

Informations

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

Extrait

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

)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

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

elbalunnatnosBteulnniassaustSes. G.ar A→ S BacSrbael arisiv.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 ε|AAa→A B A ε|BBb→B →AS