Langage algébrique

En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui est engendré par une grammaire algébrique. De manière équivalente, un langage algébrique est un langage reconnu par un automate à pile.

Les langages algébriques forment les langages de type 2 dans la hiérarchie de Chomsky. Ils ont des applications importantes dans la description des langages de programmation et en linguistique. Ils interviennent également dans la description des langages XML.

Plusieurs équivalents sont employés et équivalents : langage « context-free » ou langage non contextuel, langage hors-contexte[réf. souhaitée], langage acontextuel[1].

Quelques exemples

modifier

Les langages algébriques ont pour objectif de capturer une structure des mots qui consiste en des associations de symboles, typiquement représentées par des groupements de parenthèses ; ces mots et langages correspondent bien à des expressions structurées dans les langages de programmation (la structure begin - end, ou l'indentation) et se représentent aussi dans la hiérarchisation d'informations par des arbres, par exemple. Toutes ces possibilités dépassent les capacités d'un langage rationnel.

  • Le langage   est l'exemple type d'un langage algébrique qui n'est pas un langage rationnel. Il est formé des mots qui ont autant de lettres   que de lettres  , et avec la condition supplémentaire que les lettres   précèdent les lettres  .
  • Les langages de Dyck (ce sont des langages de mots bien parenthésées) sont des langages algébriques.
  • Les expressions arithmétiques, utilisant les quatre opérations élémentaires, par exemple  , etc., forment un langage algébrique. C'est d'ailleurs cette observation qui historiquement est à la base du développement des compilateurs qui doivent, entre autres, traduire des expressions arithmétiques complexes en les décomposant en opération élémentaires.

Pour prouver qu'un langage est algébrique, on donne une grammaire non contextuelle qui l'engendre. Voir le paragraphe d'exemples de l'article en question pour plus de détails. Pour des langages plus compliqués, on peut utiliser des méthodes plus puissantes, comme les transductions rationnelles ou le fait que les langages algébriques forment une famille abstraite de langages.

  • Le langage   est algébrique. Les mots de ce langage sont composés d'un premier groupe formé d'un certain nombre de lettres  , suivis d'autant de blocs ; chacun de ces blocs est formé de lettres   suivies du même nombre de  . Cette description donne une indication sur la manière de construire le langage : il est obtenu à partir du langage  , en substituant, à chaque lettre  , le langage  . Comme les langages algébriques sont fermés par substitution (voir ci-dessous), le langage obtenu est algébrique.
  • Le langage de Goldstine   sur deux lettres  ,   est encore plus compliqué. C'est l'ensemble des mots   ,   et   pour un   avec  . On veut donc que   ou   ou...  . Il est presque plus simple de se demander quand un mot   n'est pas dans le langage : c'est lorsque les   sont tous égaux à  , donc lorsque le mot est  .
    Pour vérifier que ce langage est algébrique, on part du langage algébrique   et on applique la substitution   Le langage   est le résultat de cette substitution.Ce langage est lié au mot infini  . En effet, le langage   est l’ensemble des mots qui ne sont pas préfixes de mots de   et qui se terminent par la lettre  .

Propriétés

modifier

Tout langage rationnel est algébrique car il peut être décrit par une grammaire régulière, qui est un cas particulier de grammaire non contextuelle.

Propriétés de clôture

modifier

La classe des langages algébriques possède certaines propriétés de clôture :

  • l'union et la concaténation de deux langages algébriques sont des langages algébriques ;
  • l'étoile d'un langage algébrique est algébrique ;
  • l'intersection de deux langages algébriques ne l'est pas nécessairement. Par exemple, l'intersection des langages   et   est  . Ce langage n'est pas algébrique (on le prouve traditionnellement à l'aide d'un lemme d'itération pour les langages algébriques). Par conséquent, la classe des langages algébriques n'est pas non plus close par complémentaire ;
  • l'image miroir d'un langage algébrique est un langage algébrique[2] ;
  • l'intersection d'un langage algébrique et d'un langage rationnel est toujours algébrique[2] ;
  • l'image homomorphe, l'image homomorphe inverse d'un langage algébrique est algébrique.

De ces propriétés, il résulte que :

Clôture par substitution

modifier

Une substitution de   dans   est une application   de   dans l'ensemble des parties de   qui est un morphisme de monoïdes, c'est-à-dire vérifie les deux propriétés :

  1.   ;
  2.   pour des mots   et  .

Dans la deuxième formule, le produit est le produit des parties de  .

Une substitution   est algébrique si   est un langage algébrique pour toute lettre  .

Le théorème de substitution affirme que si   est une substitution algébrique, alors   est un langage algébrique pour tout langage algébrique  .

Propriétés indécidables

modifier

L'appartenance d'un mot à un langage algébrique est décidable ; elle peut être testée grâce à l'algorithme CYK. On sait également décider si un langage algébrique (défini à partir d'une grammaire) est vide[3].

Mais contrairement aux langages rationnels, de nombreux autres problèmes sur les langages algébriques sont indécidables. Par exemple, il n'existe pas d'algorithme pour décider si deux langages algébriques donnés sont égaux[4]. Plus précisément, les propriétés suivantes sont indécidables. Soient  ,  ,   des langages algébriques, donnés par exemple par leurs grammaires, sur un alphabet  , et soit   un langage rationnel. Sont indécidables :

  •   ;
  •   ;
  •   ;
  •   ;
  •   ;
  •   ;
  • Le complémentaire de   est algébrique ;
  •   est algébrique ;
  •   est rationnel ;
  •   est inhéremment ambigu. Il est même indécidable qu'une grammaire donnée soit inambiguë.

Langages algébriques déterministes et inambigus

modifier

Langages déterministes

modifier

Un langage algébrique est dit déterministe s'il est reconnu par un automate à pile déterministe.

La classe des langages algébriques déterministes contient la classe des langages rationnels et est strictement incluse dans celle des langages algébriques. Le contre-exemple type de langage algébrique non déterministe est l'ensemble des palindromes.

La définition implique que l'appartenance d'un mot à un langage algébrique déterministe peut être testée en temps linéaire, contrairement au cas des langages algébriques quelconques. En outre, tout langage algébrique déterministe peut être décrit par une grammaire LR(1) et réciproquement. Cela permet de les utiliser pour des applications pratiques. Ainsi, la plupart des langages de programmation sont des langages algébriques déterministes.

La classe des langages algébriques déterministes est close par complémentaire[5]. Cependant :

  • elle n'est pas close par intersection (même contre-exemple que dans le cas non déterministe) ;
  • elle n'est pas close par union (conséquence de la clôture par complémentaire et de la non-clôture par intersection) ;
  • elle n'est pas close par concaténation (l'étoile de Kleene   du langage   défini plus haut est algébrique déterministe, mais pas  ) ;
  • elle n'est pas close par miroir, par exemple,   est algébrique déterministe mais pas  .

Langages inambigus

modifier

Un langage algébrique est inambigu ou non ambigu s'il existe une grammaire inambiguë qui l'engendre. Un langage qui n'est pas inambigu est inhéremment ambigu.

Tout langage déterministe est inambigu, mais les langages inambigus sont fermés par miroir, donc l'inclusion est stricte. Il existe des langages algébriques inhéremment ambigus, comme le langage  . Ceci se prouve à l'aide du lemme d'Ogden.

Théorèmes de représentation

modifier

Trois théorèmes donnent une façon générale de représenter les langages algébriques[6].

Théorème de Chomsky-Schützenberger

modifier

Le théorème affirme que les langages de Dyck sont des langages algébriques « typiques ».

Théorème de Chomsky-Schützenberger — Un langage   sur un alphabet   est algébrique si et seulement s'il existe un langage de Dyck  , un langage rationnel   et un morphisme alphabétique   (c'est-à-dire tel que l'image d'une lettre est une lettre ou le mot vide) tels que

 .

Théorème de Shamir

modifier

Théorème de Shamir — Un langage   sur un alphabet   est algébrique si et seulement s'il existe un alphabet  , une lettre   et un morphisme   de   dans l'ensemble des parties de   tels que

 .

Ici,   est une copie disjointe de  , et   est le langage de Dyck sur  

Théorème du langage le plus difficile, de Greibach

modifier

Le « langage le plus difficile » (hardest language en anglais) a été défini par Sheila Greibach en 1973. C'est un langage où le test d'appartenance est le plus difficile, au sens que tout algorithme de test d'appartenance se traduit en un test d'appartenance pour tout autre langage algébrique.

Étant donné un langage   sur un alphabet  , la version non déterministe de  , et le langage noté   défini comme suit. On ajoute à   les trois nouvelles lettres  . Sur ce nouvel alphabet, on considère le langage  . Tout mot   de   admet une factorisation

 

et chaque mot   lui-même s'écrit sous la forme

 

où les mots   sont sur l'alphabet  . Un choix dans   est un mot

 

obtenu en choisissant un facteur   dans chaque  . Notons   l'ensemble des choix dans  . La version non déterministe de   est défini par

 

Le langage le plus difficile est par définition le langage   qui est la version non déterministe du langage de Dyck   sur deux couples de parenthèses.

Théorème du langage le plus difficile (Greibach) — Un langage   sur un alphabet   est algébrique si et seulement s'il existe un morphisme   tel que l'on ait

 ,

  est le langage le plus difficile et   est une lettre qui n'est pas dans  .

La terminologie vient du fait que le test d'appartenance d'un mot   à   se réduit au test d'appartenance du mot   au langage  . Ainsi, tout algorithme de test d'appartenance à   fournit un algorithme général de test d'appartenance, pour les langages algébriques, de même complexité. Des extensions du théorème à des grammaires plus générales ont été proposées par Alexander Okhotin[7].

Langage algébrique et théorie de la complexité

modifier

Tout langage algébrique est décidé par un algorithme déterministe en espace O(log2 n) et en temps super-polynomial. Autrement dit, la classe des langages algébriques est incluse dans DSPACE(log2 n)[8]. Tout langage de Dyck est décidé par un algorithme déterministe en espace O(log n)[9]. De même pour les langages de parenthèses[10]. Tout langage algébrique déterministe non rationnel nécessaire au moins log n cases mémoires pour être décidé[11].

Tout langage algébrique est décidé par un algorithme déterministe en espace O(log2 n) et en temps polynomial[12]. Ainsi, tout langage algébrique est dans la classe SC.

Bibliographie

modifier

Par la nature fondamentale de cette notion, de nombreux ouvrages d'informatique théorique contiennent au moins une section sur les langages algébriques. Plusieurs livres ont également été traduits en français.

Ouvrages en français
  • Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman (trad. de l'anglais), Compilateurs : principes, techniques et outils : Avec plus de 200 exercices, Paris, Pearson, , 2e éd., 928 p. (ISBN 978-2-7440-7037-2 et 2744070378)
  • Pierre Wolper, Introduction à la calculabilité : cours et exercices corrigés, Paris, Dunod, , 3e éd., 224 p. (ISBN 2-10-049981-5).
  • Jean-Michel Autebert, Langages algébriques, Masson, , 278 p. (ISBN 978-2-225-81087-9)
  • Olivier Carton, Langages formels, calculabilité et complexité, [détail de l’édition] (lire en ligne)
  • Jean-Michel Autebert, Jean Berstel et Luc Boasson, « Context-free languages and pushdown automata », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag, (ISBN 978-3540604204), p. 111-174
Ouvrage en allemand
Ouvrages en anglais
Cours
  1. Ce sont des traductions admises sur « Langage acontextuel », TERMIUM Plus (consulté le 27 janvier 2022).
  2. a et b Hopcroft, Motwani et Ullman 2001, Chapitre 7, p. 285.
  3. Hopcroft, Motwani et Ullman 2001, Chapitre 7, p. 296.
  4. Hopcroft, Motwani et Ullman 2001, Chapitre 7, p. 302.
  5. Wolper 2006, Section 4.4.4, p. 97
  6. Autebert, Berstel, Boasson (1997)
  7. Alexander Okhotin, « Hardest languages for conjunctive and Boolean grammars », Information and Computation, vol. 266,‎ , p. 1–18 (ISSN 0890-5401, DOI 10.1016/j.ic.2018.11.001).
  8. P. M. Lewis, R. E. Stearns et J. Hartmanis, « Memory bounds for recognition of context-free and context-sensitive languages », 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965),‎ , p. 191–202 (DOI 10.1109/FOCS.1965.14, lire en ligne, consulté le ).
  9. R. W. Ritchie et F. N. Springsteel, « Language recognition by marking automata », Information and Control, vol. 20, no 4,‎ , p. 313–330 (DOI 10.1016/S0019-9958(72)90205-7, lire en ligne, consulté le ).
  10. Nancy Lynch, « Log Space Recognition and Translation of Parenthesis Languages », J. ACM, vol. 24, no 4,‎ , p. 583–590 (ISSN 0004-5411, DOI 10.1145/322033.322037, lire en ligne, consulté le ).
  11. Alt, Helmut, Mehlhorn, Kurt, Michaelson, S. et Milner, R., « Lower Bounds for the Space Complexity of Context-Free Recognition », dans Third International Colloquium on Automata, Languages and Programming, (lire en ligne).
  12. Stephen A. Cook, « Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space », Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, ACM, sTOC '79,‎ , p. 338–345 (DOI 10.1145/800135.804426, lire en ligne, consulté le ).