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 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 :

Leftmostderivations jaredwf.svg

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 ℓ b m c n ∣ m = ℓ   ou   m = n } {\displaystyle 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 ≥ 0 } {\displaystyle L_{1}=\{a^{m}b^{m}c^{n}|~m,n\geq 0\}} et L 2 = { a m b n c n |   m , n ≥ 0 } {\displaystyle 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 {\displaystyle L} est algébrique comme réunion de ces deux langages algébriques.

Les mots de L 1 ∩ L 2 {\displaystyle 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[1]. D'autres exemples sont donnés dans le livre de Harrison[2] ou dans l'ouvrage de Carton[3]. 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[3].

Exemple 3 — Le langage formé des mots x y {\displaystyle xy} , où x {\displaystyle x} et y {\displaystyle y} sont des palindromes est inhéremment ambigu[4].

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

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

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

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

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

f M ( z ) = ∑ n ≥ 0 ( 3 n ) ! n ! 3 z 3 n {\displaystyle f_{M}(z)=\sum _{n\geq 0}{\frac {(3n)!}{n!^{3}}}z^{3n}}

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

3 3 n 3 2 π n {\displaystyle 3^{3n}{\frac {\sqrt {3}}{2\pi n}}} .

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

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

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

  • ℓ = m {\displaystyle \ell =m} et m = n {\displaystyle m=n}
  • ℓ ≠ m {\displaystyle \ell \neq m} et m = n {\displaystyle m=n}
  • ℓ ≠ m {\displaystyle \ell \neq m} et m ≠ n {\displaystyle 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[7].

Démonstration

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

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

L u = { u i 1 u i 2 ⋯ u i n a i n ⋯ a i 2 a i 1 ∣ n ≥ 0 ,   1 ≤ i k ≤ m } {\displaystyle 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 ⋯ v i n a i n ⋯ a i 2 a i 1 ∣ n ≥ 0 ,   1 ≤ i k ≤ m } {\displaystyle 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 ) {\displaystyle (u_{1},v_{1}),...,(u_{m},v_{m})} admet une solution si et seulement si L u ∩ L v ≠ { ε } {\displaystyle L_{u}\cap L_{v}\neq \{\varepsilon \}} . Le langage ( L u ∪ L v ) ∖ { ε } {\displaystyle (L_{u}\cup L_{v})\setminus \{\varepsilon \}} est engendré par la grammaire avec les règles suivantes :

S → U ∣ V {\displaystyle S\to U\mid V}
U → ∑ i = 1 m u i U a i ∣ ∑ i = 1 m u i a i {\displaystyle U\to \sum _{i=1}^{m}{u_{i}Ua_{i}}\mid \sum _{i=1}^{m}{u_{i}a_{i}}}
V → ∑ i = 1 m v i V a i ∣ ∑ i = 1 m v i a i {\displaystyle 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 ∩ L v ≠ { ε } {\displaystyle 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 ) , … , ( u m , v m ) {\displaystyle (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 ) , … , ( u m , v m ) {\displaystyle (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[8].

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

Notes et références

  1. ↑ Hopcroft et Ullman 1969.
  2. ↑ Harrison 1978.
  3. ↑ a et b Carton 2014, sections 2.3.3 et 2.3.4.
  4. ↑ a b et c Berstel et Boasson 1990.
  5. ↑ Flajolet 1987.
  6. ↑ et Koechlin 2022.
  7. ↑ Hopcroft, Motwani et Ullman 2007.
  8. ↑ a et b Mateescu et Salomaa 1997 — Section 6.5 : « Ambiguity », p. 238-240.

Article connexe

  • Amphibologie

Bibliographie

  • John E. Hopcroft et Jeffrey D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (ISBN 0-201-02983-9, SUDOC 004772571).
  • Michael A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, , 594 p. (ISBN 0-201-02955-3, OCLC 266962302).
  • John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Addison Wesley, , 3e éd., xvii+535 (ISBN 978-0-321-45536-9, 0201441241 et 0-321-45536-3)
  • Olivier Carton, Langages formels, calculabilité et complexité, Paris, Vuibert, coll. « Vuibert sup maths », , 256 p. [détail de l’édition] (ISBN 978-2-311-01400-6, présentation en ligne)
  • Alexandru Mateescu et Arto Salomaa, « Aspects of Classical Language Theory », dans G. Rozenberg et A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer,
  • Jean Berstel et Luc Boasson, « Context-Free Languages », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Theoretical Computer Science, vol. B : Formal Models and Sematics, Elsevier et MIT Press, (ISBN 0-444-88074-7), p. 59-102
  • Philippe Flajolet, « Analytic models and ambiguity of context-free languages », Theoret. Comput. Sci., vol. 49,‎ , p. 283-309
  • Florent Koechlin, « New analytic techniques for proving the inherent ambiguity of context-free languages », dans 42e IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (no 250), (ISBN 978-3-95977-261-7, DOI 10.4230/LIPIcs.FSTTCS.2022.41, lire en ligne), p. 41:1–41:22.
  • icône décorative Portail de l'informatique théorique