Remarques sur les langages de parenthèses (Q800094)

Une grammaire à non-terminaux séparés, en abrégé: N.T.S., est, par définition, une grammaire algébriques \(G=<X,V,P>\) caractérisée par la propriété suivante: si une variable v engendre le mot \(\alpha\) \(m\beta\) sur (\(X\cup V)\) et si une variable w engendre le facteur m, alors v engendre le mot \(\alpha\) \(w\beta\). Une grammaire algébrique \(G=<\hat Z_ n,V,P>\) est dite grammaire de paranthèses [\textit{M. Takahashi}, Inf. Control 27, 1-36 (1975; Zbl 0291.68031)] si toutes ses règles sont de la forme (1) \(v\to zu_ 1\bar zu_ 2, z\in Z_ n, v,v_ 1,v_ 2\in V,\) ou (2) \(v\to 1\) (où 1 désigne le mot vide). Un langage est un langage de parenthèses s'il existe une grammaire de parenthèses \(G=(\hat Z_ n,V,P)\) et un sous- ensemble A de V tel que \(L_ G(A)\) soit le langage donné. On prouve ici que la famille des langages de parenthèses est une sous- classe de la famille des langages N.T.S. Par conséquent, on retrouve comme corollaire le résultat de M. Takahashi concernant les langages de parenthèses: l'égalité de deux langages de parenthèses est decidable. Ensuite, on établi deux propriétés des langages de parenthèses qui les relient aux langages parenthétiques \((=''parenthesis\) languages'') et multi-parenthétiques.