Intrinsèque ambiguïté et séries génératrices

Introduction : intrinsèque ambiguïté des langages algébriques Le but de ce chapitre est d’étudier l’intrinsèque faible ambiguïté des langages de Parikh et des langages algébriques de Parikh introduits au chapitre précédent. Comme les langages algébriques de Parikh sont une généralisation des langages algébriques, il est important d’avoir une vision générale des techniques connues sur les langages algébriques, a »n d’essayer de voir lesquelles leur sont spéci »ques, et lesquelles ont une chance de s’étendre aux modèles à compteurs. Dans cette introduction détaillée, nous présentons donc un large panel des techniques utilisées pour démontrer l’intrinsèque ambiguïté des langages algébriques. Soit Σ un alphabet « ni. Une grammaire hors-contexte G = (N, Σ, S, D) est dite non ambiguë si pour tout mot w 2 L(G), il existe exactement un arbre de dérivation de G, de racine S, et de frontière w. Du côté des automates, un automate à pile A est non ambigu si pour tout mot de w 2 L(A), il existe exactement un calcul acceptant étiqueté par w. Heureusement, ces notions coïncident pour les deux modèles dé »- nissant les langages algébriques : les constructions Nous l’avons redémontré au chapitre précédent dans le cas plus général des automates de Parikh à pile. classiques d’équivalence entre automates à pile et grammaires hors-contexte préservent facilement la non ambiguïté, si bien qu’un langage algébrique est reconnu par une grammaire hors-contexte non ambiguë si et seulement s’il est reconnu par un automate à pile non ambigu. Un langage algébrique est intrinsèquement ambigu s’il n’est reconnaissable par aucune grammaire non ambiguë (ou aucun automate à pile non ambigu). En 1961, Parikh démontre l’existence de langages algébriques intrinsèquement ambigus, en prouvant que le langage L = {a n b ma p b q | n = p ou m = q, avec n, m, p, q 2 N ⇤} est intrinsèquement ambigu ([Par61], [Par66, Theorem 3]). La preuve de Parikh utilise un argument d’itération sur les arbres de dérivation d’une grammaire non ambiguë reconnaissant le langage. Les arguments par itération de ce type sont subtils et di#ciles à mettre en place, car ils doivent s’appliquer à toute grammaire non Intrinsèque ambiguïté et séries génératrices 216 7 Intrinsèque ambiguïté et séries génératrices ambiguë reconnaissant le langage étudié. Plusieurs théorèmes ont été proposés dans le but de simpli »er, dans les preuves d’intrinsèque ambiguïté, les arguments d’itération sur les arbres de dérivation. En 1966, Ginsburg et Ullian [GU66] arrivent ainsi à caractériser exactement l’intrinsèque ambiguïté des langages algébriques Un langage L est bornés borné s’il existe des mots w1,…,wd tel que L ✓ w ⇤ 1 …w⇤ d. par une propriété sur des ensembles semilinéaires : leur équivalence permet de prouver l’intrinsèque ambiguïté de certains langages bornés par des itérations plus simples portant sur des ensembles semilinéaires, et non plus sur des arbres de dérivation. Le célèbre lemme d’Ogden [Ogd68] quant à lui simpli »e la mise en place d’itérations dans des grammaires, en facilitant l’identi »cation de paires itérantes. Au début des années 80, pour démontrer l’intrinsèque ambiguïté d’un langage non borné, les principales techniques reposent donc sur des arguments d’itération, qui s’avèrent fastidieux voire inadaptés pour étudier certains langages algébriques complexes. En 1987, Flajolet [Fla87] propose une nouvelle approche, fondée sur l’étude des séries génératrices des langages. Partant du théorème de Chomsky-Schützenberger [CS63], qui démontre que la série génératrice d’un langage algébrique non ambigu est algébrique, Flajolet démontre l’intrinsèque ambiguïté de nombreux langages, en établissant des critères simples pour montrer que leur série génératrice n’est pas algébrique. Cette nouvelle approche complète très bien les techniques d’itérations vues précédemment : ces dernières sont plutôt e#caces et rapides pour cerner les langages qui ont une structure simple, et qui auront tendance à avoir une série génératrice algébrique (par exemple, tous les langages algébriques bornés ont une série génératrice rationnelle), tandis que l’approche par séries génératrices permet de traiter rapidement des langages su#samment complexes pour avoir une série génératrice qui n’est pas algébrique.

Preuves d’intrinsèque ambiguïté par des arguments d’itération

Dans cette section, nous présentons deux outils utiles pour démontrer l’intrinsèque ambiguïté de certains langages algébriques : les critères de Ginsburg et Ullian [GU66], et le lemme d’Ogden [Ogd68]. Nous rappelons que ces deux outils ont pour objectif de simpli »er les raisonnements par itération, soit en transposant le problème sur une propriété d’ensembles semilinéaires pour les langages bornés, soit en facilitant l’identi »cation des paires itérantes dans une grammaire. 7.1 Introduction : intrinsèque ambiguïté des langages algébriques 217 Critères de Ginsburg et Ullian pour les langages bornés. Dans toute cette section, nous « xons d > 1, et Σ un alphabet Les langages algébriques sur un alphabet de taille 1 sont rationnels par le théorème de Parikh. de taille plus grande que 2. Nous « xons aussi un tuple de d mots w1,…,wd 2 Σ ⇤ , noté hwi := hw1,…,wdi. Définition 7.1 (Langages algébriques bornés, [GU66]). I Un langage L est dit borné par rapport à hwi si L ✓ w ⇤ 1 …w⇤ d . Dé »nissons la fonction fhwi : N d ! w ⇤ 1 …w⇤ d par fhwi (p1,…,pd) = w p1 1 …w pd d pour tout p 2 N d . Un langage L borné par rapport à hwi Si chaque wi est une lettre distincte de Σ, alors l’application fhwi est bijective, et sa réciproque est l’image de Parikh sur w ⇤ 1 …w⇤ d. est appelé semilinéaire si f .

Preuves d’intrinsèque ambiguïté par argument analytique : la méthode de Flajolet

En 1987, Flajolet propose une nouvelle approche pour démontrer l’intrinsèque ambiguïté de certains langages, à partir de leurs séries génératrices [Fla87]. Son article contraste avec les techniques précédemment exposées par la facilité avec laquelle il démontre l’intrinsèque ambiguïté de nombreux langages algébriques (une quinzaine!), dont certains étaient jusqu’alors inaccessibles. Comme sa méthode échoue à cerner l’intrinsèque ambiguïté des langages bornés, elle complète ainsi parfaitement les techniques usuelles par itération. En quelques mots, l’approche de Flajolet repose sur la contraposée du théorème de Chomsky-Schützenberger, qui démontre qu’un langage algébrique non ambigu possède une série génératrice algébrique. À partir de ce constat, [Fla87] a développé des critères pour montrer que certains langages algébriques sont intrinsèquement ambigus, en montrant que leur série génératrice n’est pas algébrique. Cette approche nous intéresse particulièrement, car c’est en s’inspirant des travaux de Flajolet qu’en 1993, [Mas93] a introduit sa classe LCL, puis en 2017 [CM17] la classe RCM, qui sont des classes de langages construites exprès pour avoir une série génératrice holonome Les séries holonomes constituent une classe de séries plus large que les séries algébriques. . Certains critères développés par Flajolet se généralisent ainsi naturellement pour démontrer l’intrinsèque faible ambiguïté de certains langages algébriques de Parikh.