Voir la source de Théorème de Parikh

En [[informatique théorique]], et notamment dans la théorie des [[langage algébrique|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<ref>{{article|langue=en|nom1=Parikh |prénom1=Rohit|lien auteur=Rohit Jivanlal Parikh|année=1966 |titre=On Context-Free Languages|journal=Journal of the [[Association for Computing Machinery]]|volume=13|numéro=4|url=http://portal.acm.org/citation.cfm?id=321364&dl=}}.</ref>{{,}}<ref>Une publication sous forme d'un rapport interne du MIT avec pour titre « {{Langue|en|Language Generating Devices}} », dans le ''{{Langue|en|Quarterly Progress Report}}'' du {{Langue|en|Research Laboratory of Electronics}}, {{Numéro|60}}, 1961 {{p.|199-212}}. C'est cette référence que cite Gisnburg dans son livre.</ref>, et il figure dans bon nombre de manuels d'informatique théorique<ref name="kozen">{{harvsp|Kozen|1997|loc=Supplementary Lecture H : Parikh's Theorem}}.</ref>{{,}}<ref>{{harvsp|Harrison|1978|loc= Section 6.9 : Semi-linear sets and Parikh's Theorem}}.</ref>{{,}}<ref>{{harvsp|Carton|2008|loc = Section 2.2.5 Théorème de Parikh}}.</ref>.

== Définitions et énoncé ==
Soit <math>\Sigma=\{a_1,a_2,\ldots,a_k\}</math> un [[alphabet]]. Le ''vecteur de Parikh'' d'un mot <math>w</math> est le vecteur <math>p(w)</math> de <math>\N^k</math> donné par<ref name="kozen"/> :
:<math>p(w)=(|w|_{a_1}, |w|_{a_2}, \ldots, |w|_{a_k})</math>,
où <math>|w|_{a_i}</math> dénote le nombre d'occurrences de la lettre <math>a_i</math> dans le mot <math>w</math>.

Un sous-ensemble de <math>\N^k</math> est dit ''linéaire'' s'il est de la forme
:<math>u_0+u_1\N+\cdots+ u_k\N=\{u_0+t_1u_1+\ldots+t_mu_m \mid t_1,\ldots,t_m\in\N\}</math> 
pour des vecteurs <math>u_0,\ldots,u_m</math>. C'est donc l'ensemble des combinaisons linéaires, à coefficients [[Entier naturel|entiers naturels]], d'un [[ensemble fini]] de vecteurs de <math>\N^k</math>, auxquels est ajouté le vecteur <math>u_0</math>. Par exemple, pour <math>k=3</math>, l'ensemble <math>(1,1,1)\N=\{(n,n,n)|n\in \N\}</math> est un ensemble linéaire très simple.

Un sous-ensemble de <math>\N^k</math> 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|non=Théorème de Parikh|énoncé=Pour tout langage algébrique <math>L</math>, l'ensemble <math>P(L)</math> des vecteurs de Parikh des mots de <math>L</math> 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 [[Anagramme|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 <math>H=\{(n,n,n)\mid n\in \N\}</math> des vecteurs dont les trois composantes sont égales est l'ensemble des vecteurs de Parikh d'un langage non algébrique, à savoir du langage <math>\{a^n b^n c^n \mid n \in \mathbb{N}\}</math>. Mais il y a plus : il n'existe aucun langage algébrique contenu dans <math>a^*b^*c^*</math> dont l'ensemble des vecteurs de Parikh est <math>H</math><ref>La précision « contenu dans <math>a^*b^*c^*</math> » est essentielle car le langage <math>(abc)^*</math> convient tout en étant rationnel !</ref>. Un langage contenu dans un ensemble <math>a_1^*a_2^*\cdots a_n^*</math>, où les <math>a_i</math> 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]]<ref>{{harvsp|Ginsburg|1966|loc= Chapter 5 : Bounded languages}}.</ref> 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 [[Théorème de Kleene#Généralisations et extensions|parties rationnelles du monoïde libre commutatif]]<ref>{{harvsp|Sakarovitch|2009|loc = Section II.7 : Rationals in commutative monoids}}.</ref>.

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 :

* <small>[2021]</small> {{Article 
|prénom1=Toshihiro |nom1=Koga 
|titre=A Proof of Parikh’s Theorem via Dickson’s Lemma |périodique=International Journal of Foundations of Computer Science |volume=32 |numéro=02 |date=2021-02 
|doi=10.1142/S012905412150009X|pages=163–173}}
* <small>[2021]</small> {{Article 
|prénom1=Manfred |nom1=Kufleitner 
|titre=Yet another proof of Parikh's Theorem
|périodique=Arxiv |date=2021-02 
|arxiv=2210.02925}}

* <small>[2011]</small> {{Article 
|prénom1=Javier |nom1=Esparza 
|prénom2=Pierre |nom2=Ganty 
|prénom3=Stefan |nom3=Kiefer 
|prénom4=Michael |nom4=Luttenberger 
|titre=Parikhʼs theorem: A simple and direct automaton construction |périodique=Information Processing Letters |volume=111 |numéro=12 |date=2011-06-15 
|doi=10.1016/j.ipl.2011.03.019 
|pages=614–619}}

* <small>[1977]</small> {{Article 
|prénom1=J. |nom1=Goldstine 
|titre=A simplified proof of Parikh's theorem 
|périodique=Discrete Mathematics 
|volume=19 |numéro=3 |date=1977-01-01 |doi=10.1016/0012-365X(77)90103-0 
|pages=235–239}}

* <small>[2002]</small> {{Article 
|prénom1=Luca |nom1=Aceto 
|prénom2=Zoltán |nom2=Ésik 
|prénom3=Anna |nom3=Ingólfsdóttir 
|titre=A fully equational proof of Parikh’s theorem |périodique=RAIRO - Theoretical Informatics and Applications  |volume=36 |numéro=2 |date=2002
|url=http://eudml.org/doc/244701
|pages=129-153}}

* <small>[1973]</small> {{Article 
|prénom1=D. L. |nom1=Pilling
|titre=Commutative regular equations and Parikh’s theorem
|périodique=J. London Math. Soc.
|volume=6 
|date=1973
|doi=10.1112/jlms/s2-6.4.663
|pages=663-666}}

== Notes et références ==
{{Références}}

== Bibliographie ==
* {{Ouvrage|langue=en|prénom1=Dexter|nom1=Kozen|titre=Automata and Computability|lieu=New York|éditeur=[[Springer Science+Business Media|Springer-Verlag]]|année=1997|isbn=3-540-78105-6}}.
* {{Ouvrage|langue=en|prénom1=Seymour|nom1=Ginsburg|titre=The Mathematical Theory of Context-free Languages|lieu=New York|éditeur=McGraw-Hill|année=1966}}.
* {{Ouvrage | langue=en | prénom1=Michael A. | nom1=Harrison | titre=Introduction to Formal Language Theory | éditeur=[[Addison-Wesley]] | année=1978 | pages totales=594 | isbn=0-201-02955-3 | oclc=266962302}}.
* {{Ouvrage
| langue=en
| auteur1=Jacques Sakarovitch
| titre=Elements of Automata Theory
| lieu=Cambridge
| éditeur=[[Cambridge University Press]]
| année=2009
| pages totales=758
| isbn=978-0-521-84425-3
}}. 
* {{Carton2008}}

== Article lié ==
* [[Automate de Parikh]]

{{portail|Informatique théorique}}

[[Catégorie:Langage formel]]
[[Catégorie:Théorème d'informatique|Parikh]]