Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 ! 10 - Clôture des langages algébriques 2 ! Récapitulatif On sait que la clas

1 ! 10 - Clôture des langages algébriques 2 ! Récapitulatif On sait que la classe des langages algébriques# est close pour : • lunion • la concaténation • lopération « étoile » On sait que la classe des langages algébriques# nest pas close pour : • lintersection • le complémentaire Finalement, on traite aujourdhui la construction du produit dun automate fini et dun automate à pile (avec reconnaissance sur états finals). Théorème : lintersection dun langage algébrique et dun langage rationnel est algébrique. Exemple 0 0 1 0,1 B 1 0,1 0Z!ZX 0X!XX εZ!ε" A 1X!ε" 1X!ε" 0ε!X 0Z!ZX 0X!XX 0Z!ZX 0X!XX 1X!ε" 1X!ε" 0Z!ZX 0X!XX 1X!ε" 0Z!ZX 0X!XX 0ε!X 1X!ε" 0ε!X 1X!ε" 1X!ε" εZ!ε" εZ!ε" Mots de Dyck de préfixe 00 sur lalphabet {0,1} L(A) = Mots de Dyck (non vides) sur lalphabet {0,1} 4 ! Des langages non-algébriques ? • les langages algébriques sont engendrés par les grammaires non-contextuelles et reconnus par la classe des automates à pile non-déterministes. • Tout langage est-il algébrique ? • Lensemble des langages algébriques sur un alphabet donné est dénombrable. Une grammaire peut être perçue comme un simple mot un alphabet qui serait la réunion de ses ensembles de terminaux et de non- terminaux, auquel on ajoute un nombre fini de symboles utilitaires. Cet ensemble de mots est dénombrable. • Rappel : lensemble des langages sur un alphabet donné nest pas dénombrable (cf.cours 1). Moralité : il existe des langages non-algébriques ... 5 ! Problème • Donnée : L un langage • Problème : L est-il algébrique ? En fait, existe-t-il un analogue au théorème de létoile pour les langages algébriques ? • pour les langages rationnels, on a utilisé le principe des tiroirs appliqué au nombre détats dun automate fini. • pour les langages algébriques, on utilise ce même principe sur les étiquettes des nœuds de larbre syntaxique. Idée : un arbre de dérivation suffisamment haut va contenir plusieurs sous-arbres avec le même non-terminal en racine car les non-terminaux de la grammaire sont en nombre fini. 6 ! Idée S u v w x y S u w A v x y v x A A A A 7 ! Lemme de létoile* Lemme si L est un langage algébrique, il existe un entier n ne dépendant que de L tel que : " pour tout mot µ de L de longueur ≥ n, " il existe une factorisation de µ en uvwxy telle que : i) |vx|> 0 et |w|> 0 ii) |vwx| ≤ n iii) ∀ i ≥ 0, u vi w xi y ∈ L • comme pour les langages rationnels, le lemme de létoile sert à montrer la non-algébricité dun langage. • on suppose quun langage L est algébrique et on cherche une contradiction. * Pumping lemma en anglais, aussi appelé lemme de la pompe ou même lemme du gonflement. 8 ! En pratique • on suppose L algébrique • le lemme est vérifié pour un entier n • sil existe un mot µ de L de longueur ≥ n tel que : • quelle que soit la décomposition de µ en uvwxy vérifiant : i) |vx|> 0 et |w|> 0 ii) |vwx| ≤ n • si on trouve un i ≥ 0 tel que : u vi w xi y ∉ L • alors : ➥ on peut conclure que L nest pas algébrique. 9 ! Exemple Supposition : le langage L = {0i1i2i,i>0} est algébrique • le lemme est vérifié pour un n fixé (même si on ignore sa valeur) • soit µ = 0n 1n 2n ∈ L, µ = u v w x y avec |vx|> 0, |w|> 0 et |vwx|≤ n • |vwx| ≤ n ⇒ vx ne peut contenir à la fois des 0 et des 2 • prenons i = 0 • au moins un symbole parmi 0, 1 ou 2 va voir son nombre diminuer • au moins un symbole parmi 0, 1, 2 va voir son nombre rester intact • donc il est certain que z0 = u v0 w x0 y = u w y ∉ L • pour toute factorisation de µ vérifiant les 3 conditions, il existe un i tel que zi = u vi w xi y nappartient pas à L ➨ contredit le lemme donc notre supposition est fausse ! Conclusion : L nest pas algébrique. 10 ! Démonstration • soit L un langage (supposons L = L\{ε}) et G une grammaire algébrique sous F.N. de Chomsky pour L ayant k non-terminaux • prenons µ ∈ L de longueur |µ| ≥ n = 2k • Aµ est larbre syntaxique associé à µ • fait (à montrer par simple récurrence) : si Aµ a tous ses chemins de longueur ≤ i, |µ| ≤ 2i-1 • comme |µ|> 2k-1, Aµ a un chemin C de longueur au moins k+1. • ce chemin C comporte au moins k+2 nœuds tous étiquetés par des non- terminaux sauf sa feuille, étiquetée par un terminal • donc il existe un non-terminal A apparaissant au moins 2 fois dans C et il existe deux nœuds n1 et n2 de C qui vérifient : • n1 et n2 ont la même étiquette A • n1 est plus proche de la racine que n2 • le chemin de n1 à la feuille est de longueur au plus k+1. 11 ! Démonstration (fin) • A1 engendre un facteur z de longueur ≤ 2k car sur un chemin de longueur au plus k+1 • A2 engendre w, un sous-facteur de z = v w x • v et x ne peuvent être simultanément égaux à ε : il existe une règle B → C D telle que C et D engendrent resp. v et wx (ou bien vw et x) or ni C ni D ne peut se dériver dans le vide • w est différent de ε • on a A ⇒* v A x et A ⇒* w • on constate que pour tout i ≥ 0 : A ⇒* vi w xi • on obtient une factorisation de µ en u v w x y telle que x vi w xi y ∈ L pour tout i ≥ 0. n1! A z v! x w A1! A2! A! n2 ! 12 ! Une grammaire non-algébrique* G = (N, T, P, S) • S axiome • N = {S,T} • T = {0,1,2} • P = { S 0 S T | 0 1 2 2 T T 2 1 T 2 1 1 2 2 } *ou contextuelle (context-sensitive en anglais) L(G) = { 0i1i2i,i>0 } uploads/s3/ cours-10.pdf