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 1966Modèle:,, et il figure dans bon nombre de manuels d'informatique théoriqueModèle:,Modèle:,.

Définitions et énoncé

Soit $\mathrm{\Sigma }=\{a_1,a_2,\dots ,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},\dots ,|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+\dots +t_m{u}_m\mid t_1,\dots ,t_m\in \mathbb{N}\}$

pour des vecteurs $u_0,\dots ,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 : Modèle:Théorème

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] Modèle:Article
• [2021] Modèle:Article

• [2011] Modèle:Article

• [1977] Modèle:Article

• [2002] Modèle:Article

• [1973] Modèle:Article

Bibliographie

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Carton2008

Article lié

• Automate de Parikh