Voir la source de Grammaire ambigüe

{{article principal|Grammaire algébrique}}
En [[informatique théorique]] et en [[théorie des langages]], une '''grammaire ambiguë''' ou '''ambigüe''' est une [[Grammaire non contextuelle|grammaire algébrique]] qui admet un mot avec deux dérivations gauches distinctes ou — de manière équivalente — deux [[Grammaire non contextuelle|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 [[langage de programmation|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 :
:[[Fichier:Leftmostderivations jaredwf.svg|Leftmostderivations jaredwf.svg|400px]]

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 [[palindrome]]s 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 ===
{{théorème|nom=Exemple 1|énoncé=Le langage  <math>L = \{a^\ell b^m c^n \mid m=\ell\ \text{ou}\  m=n\}</math> est algébrique et inhéremment ambigu.}}

Chacun des langages <math>L_1 = \{a^m b^m c^n |~ m,n\ge0\} </math> et <math>L_2 = \{a^m b^n c^n |~ m,n\ge0\} </math> est algébrique. Le premier est par exemple engendré par la grammaire suivante :

:S → Sc | T
:T → aTb | ε

<math>L</math> est algébrique comme réunion de ces deux langages algébriques.

Les mots de <math>L_1 \cap L_2</math> 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<ref>{{harvsp|id=HU|Hopcroft|Ullman|1969}}.</ref>. D'autres exemples sont donnés dans le livre de Harrison<ref>{{harvsp|Harrison|1978|p=}}.</ref> ou dans l'ouvrage de Carton<ref name="Carton">{{harvsp|Carton|2014|loc=sections 2.3.3 et 2.3.4.}}</ref>. 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 (combinatoire)|théorème de Chomsky-Schützenberger]], cette série est algébrique pour un langage engendré par une grammaire inambiguë.
{{théorème|nom=Exemple 2|énoncé=Le [[Langage algébrique#Quelques exemples|langage de Goldstine]] est inhéremment ambigu.}}
C'est un exemple où cette méthode s'applique<ref name="Carton"/>.
{{théorème|nom=Exemple 3|énoncé=Le langage formé des mots <math>xy</math>, où <math>x</math> et <math>y</math> sont des palindromes est inhéremment ambigu<ref name="BB">{{harvsp|Berstel|Boasson|1990}}.</ref>.}}
Alors que le langage des palindromes lui-même est inambigu.
{{théorème|nom=Exemple 1'|énoncé=Le langage des mots sur trois lettres <math>a,b</math>, et <math>c</math> formé des mots <math>w</math> tels que <math>|w|_a\ne |w|_b</math> ou <math>|w|_c\ne |w|_b</math> est inhéremment ambigu<ref name="BB"/>.}}
Ce langage est proche du premier exemple donné.
{{démonstration|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
:<math>M=\{w\mid |w|_a=|w|_b=|w|_c\}</math>
n'est pas algébrique. Or cette série est
:<math>f_M(z)=\sum_{n\ge0}\frac{(3n)!}{n!^3}z^{3n}</math>
et par la [[formule de Stirling]], le coefficient de <math>z^{3n}</math> est asymptotiquement équivalent à
:<math>3^{3n}\frac{\sqrt3}{2\pi n}</math>.
Or, d’après un résultat général de [[Philippe Flajolet]]<ref>{{harvsp|Flajolet|1987|p=}}.</ref>, un équivalent asymptotique de la forme <math>\beta^n/n</math> est caractéristique d’une fonction transcendante<ref name="BB"/>.}}

En résumé, les variantes de ces langages sont les suivants<ref>{{harvsp||Koechlin|2022}}.</ref> :
{{théorème|nom=Exemple 1"|énoncé=Les langages  <math>L = \{a^\ell b^m c^n \}</math> avec 
* <math>\ell =m</math> et <math>m= n</math>
* <math>\ell \ne m</math> et <math>m= n</math> 
* <math>\ell \ne m</math> et <math>m\ne n</math> 
sont  algébriques et inhéremment ambigus.}}

== Propriétés ==
Les [[langage algébrique déterministe|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.

{{théorème|nom=Propriété|Le problème suivant est [[Décidabilité|indécidable]] : « Une grammaire donnée, est-elle ambiguë ? ».}}
La preuve donnée ci-dessous passe par le [[problème de correspondance de Post]]<ref>{{harvsp|id=HMU|Hopcroft|Motwani|Ullman|2007}}.</ref>.

{{Démonstration/début|Titre=Démonstration}}On  [[Réduction (complexité)|réduit]] le problème de correspondance de Post au problème de l'ambiguïté.

Soit {{Math|§=<math>(u_1,v_1),\dotsc, (u_m,v_m)</math>}} une instance du problème de correspondance de Post (PCP) sur un alphabet {{Math|§=<math>\Sigma</math>}}. On introduit un nouvel alphabet {{Math|§=<math>A = \{a_1\dotsc,a_m\}</math>}} formé de {{Math|§=<math>m</math>}} lettres n'appartenant pas à {{Math|§=<math>\Sigma </math>}}. On définit, sur l'alphabet {{Math|§=<math> A \cup \Sigma </math>}} les deux langages :
:{{Math|§=<math>L_u = \{u_{i_1} u_{i_2} \dotsb u_{i_n}  a_{i_n} \dotsb a_{i_2} a_{i_1} \mid n\ge0,\ 1\le i_k \le m \} </math>}}
:{{Math|§=<math>L_v = \{v_{i_1} v_{i_2} \dotsb v_{i_n}  a_{i_n} \dotsb a_{i_2} a_{i_1} \mid n\ge0,\  1\le i_k \le m \} </math>}}.
L'instance du PCP {{Math|§=<math>(u_1,v_1),...,(u_m,v_m)</math>}} admet une solution si et seulement si {{Math|§=<math> L_u \cap L_v \ne \{\varepsilon \} </math>}}.
Le langage {{Math|§=<math> (L_u \cup L_v)\setminus \{\varepsilon \} </math>}} est engendré par la grammaire avec les règles suivantes :
:{{Math|§=
<math> S \to U \mid V</math>
:<math> U \to \sum_{i=1}^{m} {u_i U a_i} \mid \sum_{i=1}^{m} {u_i a_i}</math>
:<math> V \to \sum_{i=1}^{m} {v_i V a_i} \mid  \sum_{i=1}^{m} {v_i a_i}</math>}}
Il est facile de voir que cette grammaire est ambiguë si et seulement si {{Math|§=<math> L_u \cap L_v \ne \{\varepsilon \} </math>}} ; et que cette intersection est ne se réduit pas au mot vide si et seulement si {{Math|§=<math>(u_1,v_1),\ldots,(u_m,v_m)</math>}} admet une solution. La réduction est le calcul de la grammaire ci-dessus depuis l'instance du PCP {{Math|§=<math>(u_1,v_1),\ldots,(u_m,v_m)</math>}}. Ceci prouve que le problème de l'ambiguïté est indécidable.

{{Démonstration/fin}}

== 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.
{{théorème|nom=Propriété|Il existe des langages inhéremment ambigus pour lesquels le degré d'ambiguïté de toute grammaire est infini<ref name="MS" />.}}

La [[décidabilité]] de l'énoncé suivant est un problème ouvert (en 1977)<ref name="MS">{{harvsp|id=MS|Mateescu|Salomaa|1997|p=}} — Section 6.5 : « {{Langue|en|Ambiguity}} », {{p.|238-240}}.</ref> : « Étant donnée une grammaire, son degré d'ambiguité est-il fini ? »

== Notes et références ==
{{Références}}
== Article connexe ==
* [[Amphibologie]]

== Bibliographie ==
*{{Ouvrage|auteur1=John E. Hopcroft|auteur2=Jeffrey D. Ullman|titre=Formal Languages and Their Relation to Automata|éditeur=Addison-Wesley|année=1969|isbn=0-201-02983-9|sudoc=004772571|id=HU}}.
*{{Ouvrage | auteur1=Michael A. Harrison | titre=Introduction to Formal Language Theory | éditeur=Addison-Wesley | année=1978 | pages totales=594 | isbn=0-201-02955-3 | oclc=266962302}}.
* {{Ouvrage | auteur1=John E. Hopcroft | auteur2=Rajeev Motwani | auteur3=Jeffrey D. Ullman | titre=Introduction to Automata Theory, Languages, and Computation | éditeur=Pearson Addison Wesley | année=2007 | pages totales=xvii+535 | isbn=978-0-321-45536-9 | isbn2=0201441241 | isbn3=0-321-45536-3 | id=HMU | numéro édition=3}}
* {{Carton2}}
* {{chapitre|id=MS|auteur1=Alexandru Mateescu|auteur2=Arto Salomaa
 |titre chapitre=Aspects of Classical Language Theory
 |titre ouvrage=Handbook of Formal Languages
 |auteur ouvrage=G. Rozenberg et A. Salomaa (éditeurs)
 | volume = 1
 | titre volume = Word, Language, Grammar
 |éditeur = Springer
 |année = 1997
}}
* {{chapitre
| auteur1 =  Jean Berstel|auteur2 = Luc Boasson
| titre chapitre = Context-Free Languages
| auteurs ouvrage = G. Rozenberg, A. Salomaa (éditeurs)
| titre ouvrage = Handbook of Theoretical Computer Science
| éditeur = Elsevier et MIT Press
| année = 1990
| volume = B
| titre volume = Formal Models and Sematics
| passage  = 59-102
| isbn = 0-444-88074-7
}}
* {{Article
 | auteur = Philippe Flajolet
 | titre           = Analytic models and ambiguity of context-free languages
 | périodique      = Theoret. Comput. Sci.
 | volume          = 49
 | année           = 1987
 | pages           = 283-309
}}
* {{Chapitre |prénom1=Florent |nom1=Koechlin 
|titre=New analytic techniques for proving the inherent ambiguity of context-free languages 
|titre ouvrage = {{42e}} IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) 
|collection=Leibniz International Proceedings in Informatics (LIPIcs) 
|numéro dans collection=250 
|éditeur=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |date=2022 
|isbn=978-3-95977-261-7 
|doi=10.4230/LIPIcs.FSTTCS.2022.41 
|lire en ligne=https://drops.dagstuhl.de/opus/volltexte/2022/17433
|passage=41:1–41:22}}.

{{Portail|informatique théorique}}

[[Catégorie:Langage formel]]
[[Catégorie:Grammaire]]