×

zbMATH — the first resource for mathematics

Remarques sur les langages de parenthèses. (French) Zbl 0549.68072
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 [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.
Reviewer: R.Andonie

MSC:
68Q45 Formal languages and automata
PDF BibTeX Cite
Full Text: DOI
References:
[1] Autebert, J.-M.; Beauquier, J.; Boasson, L., Limites de langages algébriques, Compte-rend. acad. sci. Paris, Sér. A, 291, 555-558, (1980) · Zbl 0444.68065
[2] Boasson, L., Grammaires à non-terminaux séparés, (), 105-108, Lecture Notes in Computer Science
[3] Boasson, L., Un langage particulier, RAIRO inform. théor., 13, 203-215, (1979) · Zbl 0424.68042
[4] Boasson, L.; Nivat, M., Parenthesis generators, 17th IEEE symp. on foundations of computer science, 252-257, (1976)
[5] Ginsburg, S.; Goldstine, J.; Greibach, S., Uniformely erasable AFL, J. comput. system sci., 10, 165-182, (1975) · Zbl 0325.68042
[6] Greibach, S., One counter languages and the J.R.S. condition, J. comput. system sci., 10, 237-247, (1975) · Zbl 0307.68062
[7] McNaughton, R., Parenthesis languages, J. assoc. comput. Mach., 14, 490-500, (1967) · Zbl 0168.01206
[8] Sénizergues, G., Décidabilité de l’équivalence des grammaires NTS, (1981), Thèse de 3ème Cycle de l’Université Paris VII Paris
[9] Takahashi, M., Generalizations of regular sets and their application to a study of context free languages, Inform. and control, 27, 1-36, (1975) · Zbl 0291.68031
[10] Takahashi, M., Nest sets and relativised closure properties, Theoret. comput. sci., 22, 253-264, (1983) · Zbl 0497.68045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.