Grammaires de graphes et langages algébriques

Lemme de Parikh

Comme le lemme des paires itérantes, le lemme de Parikh nous donne une condition nécessaire sur la distribution des lettres des mots d’un langage algébrique. Il a été introduit en 1966 [Pa 66]. Ce lemme a suscité un vif intérêt (voir [Pi 73]), et depuis presque quarante ans, différentes approches pour le démontrer ont été présentées (voir [HK 99] et [AEI 01]). Dans ce chapitre, nous présentons une démonstration géométrique du lemme de Parikh. Cette démonstration a été publiée dans [Di 06].

Lemme de Parikh

Pour commencer, nous rappelons les définitions des ensembles linéaires, des ensembles semi-linéaires, et également la définition de l’image commutative d’un langage (voir par exemple [Re 88] et [Ha 78]). Un ensemble de la forme { α0 + k1α1 + · · · + knαn | k1, · · · ,kn ∈ N } où α0, · · · ,αn sont des élément de N m, est dit un sous-ensemble linéaire de N m. Un ensemble semi-linéaire est une union finie d’ensembles linéaires. Comme N m est un monoïde commutatif pour l’opération d’addition + composante à composante, ses ensembles semi-linéaires sont ses parties rationnelles. 26 3.2. Lemme de Parikh Y X 0 Figure 3.2 – Un ensemble linéaire. Y X 0 Figure 3.3 – Un ensemble semi-linéaire. Aussi, ils forment une algèbre de Boole [GS 64] : la famille des ensembles semilinéaires de N m est fermée par union, intersection et complémentation. Etant donné un alphabet T = {a1, · · · ,am}, nous définissons l’application ψ de T ∗ dans N m comme suit : ψ(w) = (|w|a1 , · · · , |w|am) où |w|ai désigne le nombre d’occurrences de la lettre ai dans le mot w. On dit que ψ(w) est l’image de Parikh du mot w. 27 Chapitre 3. Grammaires de graphes et langages algébriques Par exemple pour T = {a,b,c}, on a ψ(abacac) = (3, 1, 2). Soient x,y ∈ T ∗ deux mots quelconques, nous avons ψ(x.y) = ψ(x) + ψ(y) = ψ(y) + ψ(x) = ψ(y.x) En particulier, ψ est un morphisme de T ∗ dans N m. L’image de Parikh s’étend par union à tout langage L ⊆ T ∗ : ψ(L) = {ψ(x) | x ∈ L}. Comme la rationalité est préservée par morphisme, on a ψ(L) rationnel pour tout langage rationnel L. La réciproque n’est pas vraie : ψ −1 ({(0, 1) + k.(1, 2) | k ≥ 0}) ∩ a ∗ b ∗ = {a n b 2n+1|n ≥ 0}. La semi-linéarité de l’image de Parikh d’un langage rationnel se généralise à tout langage algébrique [Pa 66]. Lemme 4 (Lemme de Parikh). L’image de Parikh ψ(L) de tout langage algébrique L est de façon effective un ensemble semi-linéaire. Soit G une grammaire algébrique qui engendre le langage L et soit ψ(L) l’image de Parikh de L. Ainsi, ψ(L) est un ensemble semi-linéaire de N m. De plus, une description de ψ(L) sous la forme : ψ(L) = Q1 ∪ Q2 ∪ · · · ∪ Qn où Q1, …, Qn sont des ensembles linéaires de N m, peut être obtenue par un algorithme (déterministe) à partir de G. 3.2.3 Démonstration géométrique du lemme de Parikh Dorénavant R est une grammaire de graphes d’ensemble N = {B1,…,Bp} des non-terminaux. Soit Tr = [ n≥0 Hn avec {(1,A, 2)} = H0 =⇒R H1 … =⇒R Hn =⇒R …  un graphe engendré par R à partir d’un axiome A ∈ N et auquel on a adjoint ses arcs non-terminaux. On note Trn+1 = Hn+1 − Hn pour tout n ≥ 0. L’ensemble des non-terminaux récrits pour engendrer un chemin β de Tr est noté Λ(β); l’étiquette du chemin β se note I(β). A B E B C B B A F β F0 F1 Fi Tr1 z}|{ Tr2 z}|{ Tri z}|{ Figure 3.4 – Ensemble Λ(β) = {A,B,C,E,F}. Une réduction d’un chemin α est l’opération qui enlève une partie βB de α pour obtenir un autre chemin α ′ , comme indiqué à la figure 3.5. On dit que α se réduit en (α ′ ,βB) et on note α reduire −→ (α ′ ,βB); dans le cas où βB n’est pas pertinent, on peut l’ignorer et écrire simplement α reduire −→ α ′ . On dit que α est un chemin réductible s’il peut être réduit, sinon α est dit irréductible. Si α et α ′ appartiennent à un ensemble F de chemins, on dit que α est réductible selon F, sinon α est dit irréductible selon F. Un ensemble F de chemins est dit réductible s’il contient au moins un chemin réductible selon F ; sinon, F est dit irréductible. Remarque. Tout chemin irréductible engendré par une grammaire de graphes est de longueur bornée. Par conséquent, tout ensemble irréductible de chemins engendrés par une grammaire de graphes est fini.