Théorème de Parikh

En informatique théorique, et notamment dans la théorie des langages algébriques, le théorème de Parikh est un théorème qui compare les fréquences relatives d'apparition des lettres dans un langage algébrique. Il dit que si on compte, dans un langage formel, uniquement le nombre d'apparitions des lettres dans un mot, on ne peut pas distinguer les langages algébriques des langages rationnels.

Ce théorème a été prouvé par Rohit Parikh en 1966, et il figure dans bon nombre de manuels d'informatique théorique.

Définitions et énoncé

Soit $\Sigma =\{a_{1},a_{2},\ldots ,a_{k}\}$ un alphabet. Le vecteur de Parikh d'un mot $w$ est le vecteur $p(w)$ de $\mathbb {N} ^{k}$ donné par :

$p(w)=(|w|_{a_{1}},|w|_{a_{2}},\ldots ,|w|_{a_{k}})$,

où $|w|_{a_{i}}$ dénote le nombre d'occurrences de la lettre $a_{i}$ dans le mot $w$.

Un sous-ensemble de $\mathbb {N} ^{k}$ est dit linéaire s'il est de la forme

$u_{0}+u_{1}\mathbb {N} +\cdots +u_{k}\mathbb {N} =\{u_{0}+t_{1}u_{1}+\ldots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}$

pour des vecteurs $u_{0},\ldots ,u_{m}$. C'est donc l'ensemble des combinaisons linéaires, à coefficients entiers naturels, d'un ensemble fini de vecteurs de $\mathbb {N} ^{k}$, auxquels est ajouté le vecteur $u_{0}$. Par exemple, pour $k=3$, l'ensemble $(1,1,1)\mathbb {N} =\{(n,n,n)|n\in \mathbb {N} \}$ est un ensemble linéaire très simple.

Un sous-ensemble de $\mathbb {N} ^{k}$ est dit semi-linéaire s'il est une union finie de parties linéaires.

L'énoncé du théorème est le suivant :

Théorème — Pour tout langage algébrique $L$, l'ensemble $P(L)$ des vecteurs de Parikh des mots de $L$ est un ensemble semi-linéaire.

On peut montrer que réciproquement, tout ensemble semi-linéaire est l'ensemble des vecteurs de Parikh d'un langage rationnel.

Deux mots sont commutativement équivalents s'ils sont des anagrammes l'un de l'autre, donc s'ils ont même vecteur de Parikh. Deux langages sont dits commutativement équivalents s'ils ont même ensemble de vecteurs de Parikh. D'après la remarque précédente, tout langage algébrique est commutativement équivalent à un langage rationnel. C'est sous cette forme que l'on trouve aussi parfois une formulation du théorème de Parikh.

Développements

La réciproque du théorème de Parikh est fausse : ainsi, en dimension 3, l'ensemble linéaire $H=\{(n,n,n)\mid n\in \mathbb {N} \}$ des vecteurs dont les trois composantes sont égales est l'ensemble des vecteurs de Parikh d'un langage non algébrique, à savoir du langage $\{a^{n}b^{n}c^{n}\mid n\in \mathbb {N} \}$. Mais il y a plus : il n'existe aucun langage algébrique contenu dans $a^{*}b^{*}c^{*}$ dont l'ensemble des vecteurs de Parikh est $H$. Un langage contenu dans un ensemble $a_{1}^{*}a_{2}^{*}\cdots a_{n}^{*}$, où les $a_{i}$ sont des lettres ou plus généralement des mots, est appelé un langage borné. Ces langages ont des propriétés particulières que Seymour Ginsburg a traité dans un chapitre de son livre. Il donne une étude détaillée et une caractérisation des ensembles semi-linéaires qui correspondent à des langages algébriques bornés : il montre que les images de Parikh des langages algébriques bornés sont des ensembles semi-linéaires particuliers qu'il appelle « stratifiés ».

D'un point de vue plus algébrique, les ensembles semi-linéaires sont exactement les parties rationnelles du monoïde libre commutatif.

La simplicité de l'énoncé et la complexité de la démonstration ont suscité tout un ensemble de variantes de preuves, parmi lesquelles il y a par exemple :

• [2021] Toshihiro Koga, « A Proof of Parikh’s Theorem via Dickson’s Lemma », International Journal of Foundations of Computer Science, vol. 32, n^o 02,‎ février 2021, p. 163–173 (DOI 10.1142/S012905412150009X)
• [2021] Manfred Kufleitner, « Yet another proof of Parikh's Theorem », Arxiv,‎ février 2021 (arXiv 2210.02925)

• [2011] Javier Esparza, Pierre Ganty, Stefan Kiefer et Michael Luttenberger, « Parikhʼs theorem: A simple and direct automaton construction », Information Processing Letters, vol. 111, n^o 12,‎ 15 juin 2011, p. 614–619 (DOI 10.1016/j.ipl.2011.03.019)

• [1977] J. Goldstine, « A simplified proof of Parikh's theorem », Discrete Mathematics, vol. 19, n^o 3,‎ 1^er janvier 1977, p. 235–239 (DOI 10.1016/0012-365X(77)90103-0)

• [2002] Luca Aceto, Zoltán Ésik et Anna Ingólfsdóttir, « A fully equational proof of Parikh’s theorem », RAIRO - Theoretical Informatics and Applications, vol. 36, n^o 2,‎ 2002, p. 129-153 (lire en ligne)

• [1973] D. L. Pilling, « Commutative regular equations and Parikh’s theorem », J. London Math. Soc., vol. 6,‎ 1973, p. 663-666 (DOI 10.1112/jlms/s2-6.4.663)

Bibliographie

• (en) Dexter Kozen, Automata and Computability, New York, Springer-Verlag, 1997 (ISBN 3-540-78105-6).
• (en) Seymour Ginsburg, The Mathematical Theory of Context-free Languages, New York, McGraw-Hill, 1966.
• (en) Michael A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978, 594 p. (ISBN 0-201-02955-3, OCLC 266962302).
• (en) Jacques Sakarovitch, Elements of Automata Theory, Cambridge, Cambridge University Press, 2009, 758 p. (ISBN 978-0-521-84425-3).
• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)

Article lié

• Automate de Parikh