10:45
11:45

Un langage sans contexte est intrinsèquement ambigu si toute grammaire le reconnaissant est ambiguë, c'est-à-dire s'il existe un mot généré de deux manières différentes. Décider de l'ambiguïté inhérente d'un langage sans contexte est un problème difficile, indécidable en général. Les premiers exemples de langages intrinsèquement ambigus ont été découverts dans les années 1960, en utilisant des techniques d'itération sur les arbres de dérivation. Ils appartenaient à une sous-famille particulière de langages sans contexte, appelés langages sans contexte bornés.
Bien qu'elles aient permis de prouver l'ambiguïté inhérente de plusieurs langages, comme par exemple le langage L = a^n b^m c^p avec n=m ou m=p, les techniques d'itération restent très laborieuses à mettre en œuvre, sont très spécifiques au langage étudié, et semblent même parfois inadaptées. Par exemple, la relative simplicité de la preuve de l'ambiguïté inhérente de L s'effondre complètement en remplaçant la contrainte "n=m ou m=p" par "n≠m ou m≠p".
Dans cet exposé, je présenterai deux critères utiles basés sur les séries génératrices pour prouver facilement l'ambiguïté inhérente de nombreux langages contextuels libres bornés, en étendant un critère récent développé par Makarov en 2021. Ces langages, qui ont une série génératrice rationnelle, ont résisté à la fois aux techniques d'itération classiques développées dans les années 1960 et aux méthodes analytiques introduites par Philippe Flajolet en 1987.

Salle 76