Grammaire ambigüe
# Grammaire ambigüe

En informatique théorique et en théorie des langages, une grammaire ambiguë ou ambigüe est une grammaire algébrique qui admet un mot avec deux dérivations gauches distinctes ou — de manière équivalente — deux arbres de dérivation distincts. L'ambiguïté ou l'inambiguïté est une propriété des grammaires, et non des langages. De nombreux langages admettent à la fois des grammaires ambiguës et inambigües, alors que d'autres ne possèdent que des grammaires ambiguës. Un langage pour lequel toutes les grammaires sont ambiguës est appelé inhéremment ambigu (ou intrinsèquement ambigu), les autres sont appelés langages inambigus.

La grammaire de référence de langages de programmation est parfois ambigüe à cause de constructions qui conduisent à des problèmes comme le problème du dangling else. De telles ambiguïtés sont généralement levées en ajoutant des règles de précédence ou d'autres règles, contextuelles celles-là, qui rendent la grammaire finale inambigüe.

## Exemples

### Addition et soustraction

La grammaire algébrique définie par la règle suivante

    A → A + A | A - A | a

est ambiguë parce que le mot a + a - a possède deux dérivations gauches distinctes :

    A → A - A → A + A - A → a + A - A → a + a - A → a + a - a

et

    A → A + A → a + A → a + A - A → a + a - A → a + a - a

Dans la première, c'est la règle A → A + A qui est utilisée dans la deuxième étape ; dans la seconde, c'est au contraire la règle A → a qui est employée.

Ces dérivations donnent deux arbres de dérivation distincts :

Le langage lui-même est inambigu (c'est-à-dire n'est pas inhéremment ambigu) puisqu'il est engendré par exemple par la grammaire inambiguë que voici :

    A → A + a | A − a | a

### Palindromes

Le langage des palindromes est inambigu. Il est engendré (sur l'alphabet a,b par exemple), par la grammaire inambiguë, définie par la règle suivante :

    A → aAa | bAb | a | b | ε

### Langages algébriques inhéremment ambigus

Exemple 1 — Le langage $L=\{a^{\ell }b^{m}c^{n}\mid m=\ell \ {\text{ou}}\ m=n\}$ est algébrique et inhéremment ambigu.

Chacun des langages $L_{1}=\{a^{m}b^{m}c^{n}|~m,n\geq 0\}$ et $L_{2}=\{a^{m}b^{n}c^{n}|~m,n\geq 0\}$ est algébrique. Le premier est par exemple engendré par la grammaire suivante :

    S → Sc | T
    T → aTb | ε

$L$ est algébrique comme réunion de ces deux langages algébriques.

Les mots de $L_{1}\cap L_{2}$ posent problème. On peut prouver, à l'aide du lemme d'Ogden (la démonstration est faite sur la page correspondante), qu'il n'existe pas de grammaire inambiguë pour le langage. D'autres exemples sont donnés dans le livre de Harrison ou dans l'ouvrage de Carton. Une autre méthode pour démontrer l'ambiguïté inhérente d'un langage est de passer par la fonction génératrice qui énumère le nombre de mots de longueur donnée du langage. D'après le théorème de Chomsky-Schützenberger, cette série est algébrique pour un langage engendré par une grammaire inambiguë.

Exemple 2 — Le langage de Goldstine est inhéremment ambigu.

C'est un exemple où cette méthode s'applique.

Exemple 3 — Le langage formé des mots $xy$, où $x$ et $y$ sont des palindromes est inhéremment ambigu.

Alors que le langage des palindromes lui-même est inambigu.

Exemple 1' — Le langage des mots sur trois lettres $a,b$, et $c$ formé des mots $w$ tels que $|w|_{a}\neq |w|_{b}$ ou $|w|_{c}\neq |w|_{b}$ est inhéremment ambigu.

Ce langage est proche du premier exemple donné.

La démonstration est intéressante parce qu'elle passe par le complémentaire. On cherche à démontrer que la série génératrice du langage n'est pas algébrique. Il suffit pour cela de prouver que la série génératrice du langage complémentaire

    $M=\{w\mid |w|_{a}=|w|_{b}=|w|_{c}\}$

n'est pas algébrique. Or cette série est

    $f_{M}(z)=\sum _{n\geq 0}{\frac {(3n)!}{n!^{3}}}z^{3n}$

et par la formule de Stirling, le coefficient de $z^{3n}$ est asymptotiquement équivalent à

    $3^{3n}{\frac {\sqrt {3}}{2\pi n}}$.

Or, d’après un résultat général de Philippe Flajolet, un équivalent asymptotique de la forme $\beta ^{n}/n$ est caractéristique d’une fonction transcendante.

En résumé, les variantes de ces langages sont les suivants :

Exemple 1" — Les langages $L=\{a^{\ell }b^{m}c^{n}\}$ avec

* $\ell =m$ et $m=n$
* $\ell \neq m$ et $m=n$
* $\ell \neq m$ et $m\neq n$

sont algébriques et inhéremment ambigus.

## Propriétés

Les langages algébriques déterministes possèdent toujours une grammaire inambiguë. Ils constituent une sous-classe stricte de la famille des langages inambigus. Le langage des palindromes ci-dessus fournit un exemple de langage algébrique non déterministe mais qui est inambigu.

Propriété — Le problème suivant est indécidable : « Une grammaire donnée, est-elle ambiguë ? ».

La preuve donnée ci-dessous passe par le problème de correspondance de Post.

On réduit le problème de correspondance de Post au problème de l'ambiguïté.

Soit $(u_{1},v_{1}),\dotsc ,(u_{m},v_{m})$ une instance du problème de correspondance de Post (PCP) sur un alphabet $\Sigma$. On introduit un nouvel alphabet $A=\{a_{1}\dotsc ,a_{m}\}$ formé de $m$ lettres n'appartenant pas à $\Sigma$. On définit, sur l'alphabet $A\cup \Sigma$ les deux langages :

    $L_{u}=\{u_{i_{1}}u_{i_{2}}\dotsb u_{i_{n}}a_{i_{n}}\dotsb a_{i_{2}}a_{i_{1}}\mid n\geq 0,\ 1\leq i_{k}\leq m\}$
    $L_{v}=\{v_{i_{1}}v_{i_{2}}\dotsb v_{i_{n}}a_{i_{n}}\dotsb a_{i_{2}}a_{i_{1}}\mid n\geq 0,\ 1\leq i_{k}\leq m\}$.

L'instance du PCP $(u_{1},v_{1}),...,(u_{m},v_{m})$ admet une solution si et seulement si $L_{u}\cap L_{v}\neq \{\varepsilon \}$. Le langage $(L_{u}\cup L_{v})\setminus \{\varepsilon \}$ est engendré par la grammaire avec les règles suivantes :

    $S\to U\mid V$
    $U\to \sum _{i=1}^{m}{u_{i}Ua_{i}}\mid \sum _{i=1}^{m}{u_{i}a_{i}}$
    $V\to \sum _{i=1}^{m}{v_{i}Va_{i}}\mid \sum _{i=1}^{m}{v_{i}a_{i}}$

Il est facile de voir que cette grammaire est ambiguë si et seulement si $L_{u}\cap L_{v}\neq \{\varepsilon \}$ ; et que cette intersection est ne se réduit pas au mot vide si et seulement si $(u_{1},v_{1}),\ldots ,(u_{m},v_{m})$ admet une solution. La réduction est le calcul de la grammaire ci-dessus depuis l'instance du PCP $(u_{1},v_{1}),\ldots ,(u_{m},v_{m})$. Ceci prouve que le problème de l'ambiguïté est indécidable.

## Degré d'ambiguïté

Le degré d'ambiguïté d'un mot w engendré par une grammaire est le nombre de dérivations gauches, différentes, qui permettent d'aboutir au mot w. Le degré d'ambiguïté d'une grammaire est le maximum (éventuellement infini) des degrés des mots engendrés par cette grammaire.

Propriété — Il existe des langages inhéremment ambigus pour lesquels le degré d'ambiguïté de toute grammaire est infini.

La décidabilité de l'énoncé suivant est un problème ouvert (en 1977) : « Étant donnée une grammaire, son degré d'ambiguité est-il fini ? »

