Théorème de Parikh

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

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

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

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

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

Un sous-ensemble de ${\displaystyle \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 :

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.

La réciproque du théorème de Parikh est fausse : ainsi, en dimension 3, l'ensemble linéaire ${\displaystyle 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 ${\displaystyle \{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 ${\displaystyle a^{*}b^{*}c^{*}}$ dont l'ensemble des vecteurs de Parikh est ${\displaystyle H}$[6]. Un langage contenu dans un ensemble ${\displaystyle a_{1}^{*}a_{2}^{*}\cdots a_{n}^{*}}$, où les ${\displaystyle 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[7] 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[8].

• (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)

• Automate de Parikh

• Portail de l'informatique théorique