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

Stef Graillat

Description

Calculabilité - Décidabilité (LI347)oCours n 8Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚8) 1 / 32Résumé du cours précédentGrammaire et automate à pile : les langages acceptés par un AP soitpar état final soit par pile vide sont exactement les langageshors-contexteAutomate à pile déterministe : un automate à pile est déterministe s’iln’a jamais le choix de mouvement étant donné un état, un symboled’entrée et un symbole de pileLangage accepté par un APD : tous les langages réguliers sontacceptés (par état final) par un APD. Les langages acceptés par unAPD sont hors-contexte et ont une grammaire non-ambigue. Leslangages acceptés par un APD contiennent strictement les langagesréguliers et sont inclus strictement dans les langages hors-contexteÉlimination des symboles inutiles : une variable peut être éliminéed’une grammaire à moins que l’on puisse y dériver une chaine determinaux et qu’elle apparaisse aussi dans une dérivation depuis lesymbole de départS. Graillat (Univ. Paris 6) LI347 (cours n˚8) 2 / 32Résumé du cours précédent (suite)Élimination des ε-productions et des productions unitaires : étantdonnée une grammaire, on pour trouver une autre grammairereconnaissant le même langage (excepté ε) mais sans ε-production etsans production unitaire (les règles avec seulement une variable dans lecorps)Forme normale de Chomsky : étant donnée une grammaire, on peutconstruire une autre grammaire ...

Informations

• Publié par: Erda
• Nombre de lectures: 78
• Langue: Français

Extrait

Calculabilité - Décidabilité (LI347) Cours n o 8

S. Graillat (Univ. Paris 6)

Stef Graillat

Université Pierre et Marie Curie (Paris 6)

LI347 (cours n˚8)

Résumé du cours précédent

1 / 32

Grammaire et automate à pile : les langages acceptés par un AP soit par état final soit par pile vide sont exactement les langages hors-contexte Automate à pile déterministe : un automate à pile est déterministe s’il n’a jamais le choix de mouvement étant donné un état, un symbole d’entrée et un symbole de pile Langage accepté par un APD : tous les langages réguliers sont acceptés (par état final) par un APD. Les langages acceptés par un APD sont hors-contexte et ont une grammaire non-ambigue . Les langages acceptés par un APD contiennent strictement les langages réguliers et sont inclus strictement dans les langages hors-contexte Élimination des symboles inutiles : une variable peut être éliminée d’ maire à moins que l’on puisse y dériver une chaine de une gram terminaux et qu’elle apparaisse aussi dans une dérivation depuis le symbole de départ

S. Graillat (Univ. Paris 6) LI347 (cours n˚8)

2 / 32

Résumé du cours précédent (suite)

Élimination des ε -productions et des productions unitaires : étant donnée une grammaire, on pour trouver une autre grammaire reconnaissant le même langage (excepté ε ) mais sans ε -production et sans production unitaire (les règles avec seulement une variable dans le corps) Forme normale de Chomsky : étant donnée une grammaire, on peut construire une autre grammaire générant le même langage (excepté ε ) sous forme normale de Chomsky : il n’y a pas de symbole inutile, et le corps de chaque règle de production consiste soit en deux variables soit en un terminal

S. Graillat (Univ. Paris 6)

LI347 (cours n˚8)

Forme normale de Chomsky

Théorème 1 Tout langage hors-contexte ne contenant pas ε peut être défini par une grammaire dont les productions sont de la forme suivante : A → BC où A, B et C sont des variables, A → a où A est une variable et a un terminal.

3 / 32

Algorithme 1 (Mise sous forme normale) Partir d’une grammaire sans symbole inutile, sans ε -production et sans production unitaire. (a) Modifier les corps des productions pour que ceux de longueur 2 ou plus ne contiennent que des variables. (b) Scinder les corps de longueur 3 ou plus en une cascade de productions dont les corps ne contiennent que deux variables.

.SrGialltaU(inv.Paris6)IL437(cours˚n)84/23

Forme normale de Chomsky (suite)

(a) Modifier les corps des productions pour que ceux de longueur 2 ou plus ne contiennent que des variables. Si un terminal a apparait dans le corps d’une règle de longueur 2 ou plus, on crée une nouvelle variable, par exemple A et on remplace a par A dans toutes les règles. On ajoute ensuite la règle A → a . (b) Scinder les corps de longueur 3 ou plus en une cascade de productions dont les corps ne contiennent que deux variables. Pour chaque règle de la forme A → B 1 B 2 ∙ ∙ ∙ B k , k ≥ 3, on introduit des nouvelles variables C 1 , C 2 , . . . , C k − 2 et on remplace la règle par A → B 1 C 1 C 1 → B 2 C 2 ∙ ∙ ∙ C k − 3 → B k − 2 C k − 2 C k − 2 → B k − 1 B k

S. Graillat (Univ. Paris 6) LI347 (cours n˚8)

Forme normale de Chomsky : exemple

Exemple : grammaire déjà simplifiée E → E + F | T ∗ F | ( E ) | a | b | Ia | Ib | I 0 | I 1 T → T ∗ F | ( E ) | a | b | Ia | Ib | I 0 | I 1 F → ( E ) | a | b | Ia | Ib | I 0 | I 1 I → a | b | Ia | Ib | I 0 | I 1

À l’ étape (a) , on a besoin des règles A → a , B → b , Z → 0, O → 1, P → + , M → ∗ , L → ( , R → ) et en remplaçant dans la grammaire, on obtient E → EPF | TMF | LER | a | b | IA | IB | IZ | IO T → TMF | LER | a | b | IA | IB | IZ | IO F → LER | a | b | IA | IB | IZ | IO I → a | b | IA | IB | IZ | IO A → a , B → b , Z → 0 , O → 1 , P → + , M → ∗ , L → ( , R → )

S.Graillat(Univ.Paris)6IL437(cours˚n)8

5 / 32

6/23

G.S(7ocrunssi)6IL43Univ.Parraillat(

À l’ étape (b) , on remplace E → EPT par E → EC 1 , C 1 → PT E → TMF , T → TMF par E → TC 2 , T → TC 2 , C 2 → MF E → LER , T → LER , F → LER par E → LC 3 , T → LC 3 , F → LC 3 , C 3 → ER Une forme normale de Chomsky de la grammaire est donc

Forme normale de Chomsky : exemple

S. Graillat (Univ. Paris 6) LI347 (cours n˚8)

E → EC 1 | TC 2 | LC 3 | a | b | IA | IB | IZ | IO T → TC 2 | LC 3 | a | b | IA | IB | IZ | IO F → LC 3 | a | b | IA | IB | IZ | I 0 I → a | b | IA | IB | IZ | IO A → a , B → b , Z → 0 , O → 1 , P → + , M → ∗ , L → ( , R → ) C 1 → PT , C 2 → MF , C 3 → ER

Le lemme de pompage pour les langages hors-contexte

7 / 32

Un outil pour prouver que certains langages ne sont pas hors-contexte

Lemme 1 (Lemme de pompage) Soit L un langage hors-contexte. Il existe un entier n tel que si z ∈ L et | z | ≥ n, alors on peut écrire z = uvwxy avec : | vwx | ≤ n vx 6 = ε pour tout i ≥ 0 , uv i wx i y ∈ L

8˚8)3/2

Pour tout mot assez long d’un langage hors-contexte, on peut trouver deux sous-mots qu’on peut répéter un nombre arbitraire de fois en tandem : le mot obtenu est encore dans le langage hors-contexte

Élément de preuve du lemme de pompage

Pour un mot z suffisament long, un arbre de dérivation pour z doit avoir une variable qui est présente au moins 2 fois dans un chemin menant de la racine à une feuille

A 0 A 1 A 2 A k a

S Supposons donc que A i = A j et telle que la forme syntaxique soit A i = A j z = uvwxy où w est la forme syntaxique géneré par le sous-arbre A j A j et vwx est la forme syntaxique géneré par le sous-arbre A i u v  w  x  y S. Graillat (Univ. Paris 6) LI347 (cours n˚8)

Élément de preuve du lemme de pompage

S S S  A A A  A A w  u v  A  x  y u v w  x  y  u  y  v  w  x On peut alors remplacer l’arbre A i par l’arbre A j ce qui donne la forme syntaxique uwy (correspondant au cas i = 0), qui appartient à L . On peut aussi remplacer l’arbre A j par l’arbre A i ce qui donne la forme syntaxique uv 2 wx 2 y (correspondant au cas i = 2), qui appartient à L . etc.

S.Graillat(Univ.Paris6)LI347c(ours˚n)81

9 / 32

0/32

Exemples d’applications du lemme de pompage

Exemple 1 : L = { 0 n 1 n 2 n | n ∈ N } Supposons L hors-contexte. Soit n donné par le lemme de pompage et z = 0 n 1 n 2 n . On peut alors découper z en z = uvwxy avec | vwx | ≤ n et vx 6 = ε . On remarque que vwx ne peut contenir à la fois des 0 et des 2 puisqu’entre le dernier 0 et le premier 2 il y a n + 1 positions. Deux cas sont possibles : vwx n’a pas de 2. Alors vx n’a que des 0 et des 1. Par conséquent, uwy qui doit être dans L a n 2 mais moins de n 0 et 1 vwx n’a pas de 0. Alors vx n’a que des 1 et des 2. Par conséquent ; uwy qui doit être dans L a n 0 mais moins de n 1 et 2 Par conséquent L n’est pas hors-contexte

S. Graillat (Univ. Paris 6) LI347 (cours n˚8)

Exemples d’applications du lemme de pompage (suite)

11 / 32

Exemple 2 : L = { 0 i 1 j 2 i 3 j | ( i , j ) ∈ N 2 } Supposons L hors-contexte. Soit n donné par le lemme de pompage et z = 0 n 1 n 2 n 3 n . On peut alors découper z en z = uvwxy avec | vwx | ≤ n et vx 6 = ε . On remarque que vwx contient un ou deux symboles différents si vwx n’a qu’un symbole alors uwy a n occurences de trois symboles différents et strictement moins de n occurrences du quatrième. Donc uwy ne peut appartenir à L si vwx contient deux symboles, par exemple 1 et 2 alors uwy manque soit de 1 soit de 2 soit des deux Par conséquent L n’est pas hors-contexte

S. Graillat (Univ. Paris 6) LI347 (cours n˚8)

12 / 32

Σ ∗ ,ondéfinit s(L)= w [ L∈ (s)w ’Lpalpci findés(it=sw) 1 )(as∙∙∙) n a(opte ⊂L ru )=L a , s(a w∈Σ ∗ Pour=w 1 avace, n no∙∙a∙ leboymtsasonΣ,a∈lnueicos a Legagna n a n baan:.)(s)1{= n+2 :n≥1}≥1}∪{a n b }bb, ruoP )1(saa{= w)s((0=s 01w=na,o }1te{=,0elΣ:expm≥1},b n :n={a n s(0) eéleppatsesnoitan E ioutitstubesun 148)2/3

S. Graillat (Univ. Paris 6)

LI347 (cours n˚8)

Substitutions

Propriétés de fermeture des langages hors-contexte

13 / 32

Quelques nuances avec les propriétés de fermeture des langages réguliers

6sL)3I74c(uosr˚naillat(Univ.Pari n,0≥k: k n rG.S }1≥ i b nn 21 ab n k ba n ∙∙ 2 ∙s(0(L(=)a{ 1 n ))= ∗ L={0Pourors s } ∗ al ouàtetetabphalunΣtioS

.vaPU(inL)3Iir6sours47(c16/3n˚8)S.atllaiGr

Substitutions (suite)

Théorème 2 Si L est un langage hors-contexte construit sur Σ , et s une substitution telle que pour tout a ∈ Σ , s ( a ) est hors-contexte, alors s ( L ) est hors-contexte. Idée de la preuve : soit G = ( V , Σ , P , S ) une grammaire pour L et G a = ( V a , T a , P a , S a ) des grammaires pour s ( a ) . Construisons la grammaire G 0 = ( V 0 , T 0 , P 0 , S ) avec V 0 = ( S a ∈ Σ V a ) S V T 0 = S a ∈ Σ T a P 0 = S a ∈ Σ P a plus les productions de P dans lesquelles chaque a est remplacé par le symbole S a

2

S. Graillat (Univ. Paris 6)

Applications des substitutions

L ( G 0 ) = s ( L )

Théorème 3 Soit L 1 et L 2 des langages hors-contexte. Alors les langages suivant sont encore hors-contexte : 1 union : L 1 ∪ L 2 2 concaténation : L 1 . L 2 3 clôture et clôture positive : L ∗ 1 et L 1 + Preuve : 1 soit L = { 1 , 2 } et s ( 1 ) = L 1 , s ( 2 ) = L 2 alors L 1 ∪ L 2 = s ( L ) 2 soit L = { 12 } et s ( 1 ) = L 1 , s ( 2 ) = L 2 alors L 1 . L 2 = s ( L ) 3 soit L = { 1 } ∗ et s ( 1 ) = L 1 alors L ∗ 1 = s ( L ) soit L = { 1 } + et s ( 1 ) = L 1 alors L 1 + = s ( L )

15 / 32

LI347 (cours n˚8)

rshoon-cxtte S. e. ’uqu’nliiatésapt ris6)LI347(coursrGialltaU(in.vaP

Théorème 4 Soit L un langage hors-contexte. Alors L R est encore un langage hors-contexte.

Preuve : Comme L est hors-contexte, L est généré par une grammaire G = ( V , T , P , S ) . Construisons G R = ( V , T , P R , S ) avec P R = { A → α R : A → α ∈ P } On peut alors montrer par induction sur la longueur de dérivation que L ( G ) R = L ( G R ) . 

3/81)8˚n

17 / 32

LI347 (cours n˚8)

S. Graillat (Univ. Paris 6)

Renversement

Intersection avec un langage régulier Contrairement aux langages réguliers, les langages hors-contexte ne sont pas clos par intersection. Soit L 1 = { 0 n 1 n 2 i : n ≥ 1 , i ≥ 1 } . Le langage L 1 est hors-contexte car reconnu par la grammaire

S → AB A → 0 A 1 | 01 B → 2 B | 2 Soit L 2 = { 0 i 1 n 2 n : n ≥ 1 , i ≥ 1 } . Le langage L 2 est hors-contexte car reconnu par la grammaire

2 |2B1→B 0|A0→A BA→S novaodtn∈n}N2 n | n {0 n 1∩L 2 =isL 1 12 Ma

Intersection avec un langage régulier Théorème 5 Si L est un langage hors-contexte et R un langage régulier, alors L ∩ R est un langage hors-contexte. Preuve : soit L accepté par l’AP P = ( Q P , Σ , Γ , δ P , q P , Z 0 , F P ) par état final et soit R accepté par l’AF A = ( Q A , Σ , δ A , q A , F A ) . On construit un AP pour L ∩ R de la façon suivante :

S. Graillat (Univ. Paris 6)

LI347 (cours n˚8)

Intersection avec un langage régulier (suite)

Formellement on définit P 0 = ( Q P × Q A , Σ , Γ , δ, ( q P , q A ) , Z 0 , F P × F A ) avec b δ (( q , p ) , a , X ) = { (( r , δ A ( p , a )) , γ ) : ( r , γ ) ∈ δ P ( q , a , X ) } On montre alors que ( q P , w , Z 0 ) ` ∗ ( q , ε, γ ) dans P si et seulement si b (( q P , Q A ) , w , Z 0 ) ` ∗ (( q , δ ( p A , w )) , ε, γ ) dans P 0

S.GraillatU(in.vaPirs6)IL437(coursn˚8)

19 / 32

20/23

Intersection avec un langage régulier (suite)

Théorème 6 Soit L, L 1 et L 2 des langages hors-contexte, R un langage régulier. Alors 1 L \ R est un langage hors-contexte. 2 L n’est pas nécessairement hors-contexte. 3 L 1 \ L 2 n’est pas nécessairement hors-contexte. Preuve : 1 R est régulier et donc L \ R = L ∩ R est hors-contexte 2 si L était toujours hors-contexte alors L 1 ∩ L 2 = L 1 ∪ L 2 serait toujours hors-contexte 3 Σ ∗ est hors-contexte donc L 1 \ L 2 était toujours hors-contexte alors Σ ∗ \ L = L serait toujours hors-contexte S. Graillat (Univ. Paris 6) LI347 (cours n˚8) 21 / 32

Propriétés de décision sur les grammaires hors-contexte

Tests classiques : Un langage hors-contexte est-il vide ? Un mot donné appartient-il à un langage hors-contexte ?

S.Graillat

Problèmes sans solution algorithmique
indécidabilité

U(in.vaPirs6)LI347(coursn˚8)22/23