Calculabilité - Décidabilité (LI347) [0.3cm] Cours no8
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 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 ...
Voir
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
À 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
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.Parin,0≥k:knrG.S}1≥ibnn21abnkban∙∙2∙s(0(L(=)a{1n))=∗L={0Pourorss}∗alouàtetetabphalunΣtioS
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)
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→B0|A0→ABA→Snovaodtn∈n}N2n|n{0n1∩L2=isL112Ma
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
