Langage algébrique déterministe

En informatique théorique et en théorie des langages, un langage algébrique déterministe est un langage algébrique reconnu (par états finals) par un automate à pile déterministe. L'intérêt des langages déterministes est que leur analyse syntaxique se fait en temps linéaire en la longueur du mot, alors que dans un langage algébrique quelconque, la complexité est cubique, ou en tout cas se ramène à la complexité du produit matriciel, donc est en O(n^2,37) où n est la longueur du mot par l'algorithme de Valiant. 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.

Exemples

• Le langage $\{a^{n}b^{n}\mid n\geq 0\}$ est déterministe.
• Le langage $\{wcw^{r}\mid w\in \{a,b\}^{*}\}$, où $c$ est une lettre différente de $a,b$, et où $w^{r}$ est le retourné de $w$, est déterministe.

Propriétés

La classe des langages algébriques déterministes contient strictement la classe des langages rationnels et est strictement incluse dans celle des langages algébriques, et même des langages algébriques inambigus.

Le contre-exemple type de langage algébrique non déterministe est l'ensemble des palindromes.

La classe des langages algébriques déterministes est close par complémentaire. 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 union) ;
• elle n'est pas close par concaténation ;
• elle n'est pas close par miroir, par exemple, $\{ca^{n}b^{n}\}\cup \{da^{2n}b^{n}\}$ est algébrique déterministe mais pas $\{b^{n}a^{n}c\}\cup \{b^{n}a^{2n}d\}$.

Exemples de langages non déterministes

• Le langage $\{a^{n}b^{n}\mid n\geq 0\}\cup \{a^{n}b^{2n}\mid n\geq 0\}$ n'est pas déterministe.
• Le langage $\{w\mid w=uv,|u|=|v|,|v|_{a}\geq 1\}$ n'est pas déterministe sur un alphabet à au moins deux lettres. Ce langage est formé des mots dont la deuxième moitié contient au moins une occurrence de la lettre $a$.
• Le langage des palindromes n'est pas déterministe.

Le principe de construction de ces langages est le même : l'automate à pile doit prendre une décision sans connaître la totalité de la donnée ; dans le premier exemple, il doit anticiper si le nombre de b est égal au ou le double du nombre de a, dans le deuxième exemple, il doit tester la présence de la lettre a dans la deuxième moitié sans savoir s'il est déjà dans la deuxième moitié.

Il existe un lemme d'itération spécial pour les langages algébriques déterministes qui permet de prouver formellement qu'un langage n'est pas déterministe. L'énoncé est assez compliqué. Une variante de ce lemme, tout aussi compliquée, est donnée par Sheng Yu.

Bibliographie

• (en) Michael A. Harrison, Introduction to Formal Language Theory, Reading, Mass., Addison-Wesley, 1978, 594 p. (ISBN 0-201-02955-3, OCLC 266962302)
• Pierre Wolper, Introduction à la calculabilité : cours et exercices corrigés, Paris, Dunod, 2006, 3^e éd., 224 p. (ISBN 2-10-049981-5).
• Sheng Yu, « A pumping lemma for deterministic context-free languages », Information Processing Letters, vol. 31, n^o 1,‎ 1989, p. 47–51 (DOI 10.1016/0020-0190(89)90108-7)