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[1],[2], et il figure dans bon nombre de manuels d'informatique théorique[3],[4],[5].

Définitions et énoncé

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

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

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

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

u 0 + u 1 N + ⋯ + u k N = { u 0 + t 1 u 1 + … + t m u m ∣ t 1 , … , t m ∈ N } {\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 u 0 , … , u m {\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 N k {\displaystyle \mathbb {N} ^{k}} , auxquels est ajouté le vecteur u 0 {\displaystyle u_{0}} . Par exemple, pour k = 3 {\displaystyle k=3} , l'ensemble ( 1 , 1 , 1 ) N = { ( n , n , n ) | n ∈ N } {\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 N k {\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 :

Théorème — Pour tout langage algébrique L {\displaystyle L} , l'ensemble P ( L ) {\displaystyle P(L)} des vecteurs de Parikh des mots de L {\displaystyle 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 ) ∣ n ∈ N } {\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 { a n b n c n ∣ n ∈ N } {\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 a ∗ b ∗ c ∗ {\displaystyle a^{*}b^{*}c^{*}} dont l'ensemble des vecteurs de Parikh est H {\displaystyle H} [6]. Un langage contenu dans un ensemble a 1 ∗ a 2 ∗ ⋯ a n ∗ {\displaystyle a_{1}^{*}a_{2}^{*}\cdots a_{n}^{*}} , où les a i {\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].

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, no 02,‎ , p. 163–173 (DOI 10.1142/S012905412150009X)
  • [2021] Manfred Kufleitner, « Yet another proof of Parikh's Theorem », Arxiv,‎ (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, no 12,‎ , 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, no 3,‎ , 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, no 2,‎ , p. 129-153 (lire en ligne)
  • [1973] D. L. Pilling, « Commutative regular equations and Parikh’s theorem », J. London Math. Soc., vol. 6,‎ , p. 663-666 (DOI 10.1112/jlms/s2-6.4.663)

Notes et références

  1. ↑ (en) Rohit Parikh, « On Context-Free Languages », Journal of the Association for Computing Machinery, vol. 13, no 4,‎ (lire en ligne).
  2. ↑ Une publication sous forme d'un rapport interne du MIT avec pour titre « Language Generating Devices », dans le Quarterly Progress Report du Research Laboratory of Electronics, no 60, 1961 p. 199-212. C'est cette référence que cite Gisnburg dans son livre.
  3. ↑ a et b Kozen 1997, Supplementary Lecture H : Parikh's Theorem.
  4. ↑ Harrison 1978, Section 6.9 : Semi-linear sets and Parikh's Theorem.
  5. ↑ Carton 2008, Section 2.2.5 Théorème de Parikh.
  6. ↑ La précision « contenu dans a ∗ b ∗ c ∗ {\displaystyle a^{*}b^{*}c^{*}}  » est essentielle car le langage ( a b c ) ∗ {\displaystyle (abc)^{*}} convient tout en étant rationnel !
  7. ↑ Ginsburg 1966, Chapter 5 : Bounded languages.
  8. ↑ Sakarovitch 2009, Section II.7 : Rationals in commutative monoids.

Bibliographie

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

Article lié

  • icône décorative Portail de l'informatique théorique