Remerciez-le!

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

Cours 10 - Clôture des langages algébriques Exemple B A Z ZX X XX X X X Z ZX X X XX X X Z L A Mots de Dyck non vides sur l alphabet X Z Z ZX X XX X Z ZX X XX Z ZX X XX X X X Z Mots de Dyck de pré ?xe sur l

- Clôture des langages algébriques Exemple B A Z ZX X XX X X X Z ZX X X XX X X Z L A Mots de Dyck non vides sur l alphabet X Z Z ZX X XX X Z ZX X XX Z ZX X XX X X X Z Mots de Dyck de pré ?xe sur l alphabet Récapitulatif On sait que la classe des langages algébriques est close pour ? ? l union ? ? la concaténation ? ? l opération étoile ? On sait que la classe des langages algébriques n est pas close pour ? ? l intersection ? ? le complémentaire Finalement on traite aujourd hui la construction du produit d un automate ?ni et d un automate à pile avec reconnaissance sur états ?nals Théorème l intersection d un langage algébrique et d un langage rationnel est algébrique 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 ? ? L ensemble 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 nonterminaux auquel on ajoute un nombre ?ni de symboles utilitaires Cet ensemble de mots est dénombrable ? ? Rappel l ensemble des langages sur un alphabet donné n est pas dénombrable cf cours Moralité il existe des langages non-algébriques CProblè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 d un automate ?ni ? ? pour les langages algébriques on utilise ce même principe sur les étiquettes des n ?uds de l arbre syntaxique Idée un arbre de dérivation su ?samment haut va contenir plusieurs sous-arbres avec le même non-terminal en racine car les non-terminaux de la grammaire sont en nombre ?ni 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 et w ii vwx ? n iii ?? i ? u vi w xi y ?? L ? ? comme pour les langages rationnels le lemme de l étoile sert à montrer la non-algébricité d un langage ? ? on suppose qu un 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 gon ement Idée S S A A A uvw x y A uv xy A v wx En pratique ? ? on suppose L algébrique ? ? le lemme est véri ?é pour un entier n ? ? s il existe