×

Contextual grammars vs. context-free algebras. (English) Zbl 0534.68050

On the basis of 27 formal definitions, the author elaborates on the relationship between contextual grammars and context-free algebras, eventually arriving at effective linear equivalents for some types of those grammars, e.g.: labelled contextual grammars are equivalent to linear grammars, and vice versa; proper contextual grammars are equivalent to linear grammars with exactly one nonterminal symbol, and vice versa.
Reviewer: M.Armbrust

MSC:

68Q45 Formal languages and automata
08A55 Partial algebras
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] Birkhoff G., Frink O.: Representation of lattices by sets. Trans. Amer. Math. Soc. 64 (1948), 299-316. · Zbl 0032.00504
[2] Birkhoff G., Lipson J. D.: Heterogeneous algebras. J. Combin. Theory 8 (1970), 115-132. · Zbl 0211.02003
[3] Cohn P. M.: Universal algebra. Harper & Row, New York, 1965. · Zbl 0141.01002
[4] Ginsburg S.: The mathematical theory of context free languages. McGraw-Hill, New York, 1966. · Zbl 0184.28401
[5] Gladkiĭ A. V.: Formaľnye grammatiki i jazyki. Nauka, Moskva, 1973.
[6] Gluškov V. M., Ceĭtlin G. E., Juščenko E. L.: Algebra, jazyki, programmirovanie. Naukova dumka, Kiev, 1974.
[7] Gruska J.: On a classification of context-free languages. Kybernetika (Prague) 3, Nr. 1 (1967), 22-29. · Zbl 0158.25401
[8] Gruska J.: Descriptional complexity of context-free languages. Mathematical Foundations of Computer Science. Proceedings of Symposium and Summer School. High Tatra, September 3-8, 1973 (1973), 71-83.
[9] Higgins P. J.: Algebras with a scheme of operators. Math. Nachr. 27 (1963/64), 115 - 132. · Zbl 0117.25903
[10] Istrail S.: O problemă despre gramaticile contextuale. Stud. Cerc. Mat. 30 (1978), 135-140.
[11] Istrail S.: Gramatici contextuale cu selectivitate regulată. Stud. Cerc. Mat. 30 (1978), 287-294.
[12] Letičevskii A. A.: Sintaksis i semantika formaľnyh jazykov. Kibernetika (Kiev), No 4 (1968), 1-9.
[13] Marcus S.: Contextual grammars. Rev. Roumaine Math. Pures Appl. 14 (1969), 1525-1534. · Zbl 0193.32401
[14] Novotný M.: On a class of contextual grammars. Cahiers Linguistique Théor. Appl. 11, Fasc. 2 (1974), 313-315.
[15] Novotný M.: On some variants of contextual languages. Rev. Roumaine Math. Pures Appl. 21 (1976), 1053-1062. · Zbl 0363.68122
[16] Păun G.: Asupra gramaticilor contextuale. Stud. Cerc. Mat. 26 (1974), 1111 - 1129.
[17] Păun G.: On the smallest number of nonterminals required to generate a context-free language. Rev. Anal. Numér. Théor. Approx. 18 (41), t. 2 (1976), 203 - 208. · Zbl 0381.68059
[18] Păun G.: Contextual grammars with restrictions in derivation. Rev. Roumaine Math. Pures Appl. 22 (1977), 1147-1154. · Zbl 0374.68052
[19] Păun G.: Operaţii cu gramatici şi limbaje contextuale. Stud. Cerc. Mat. 30 (1978), 425-439.
[20] Păun G.: On some classes of contextual grammars. Bull. Math. Soc. Sci. Math. R.S. Roumanie 22 (70) (1978), 183-189. · Zbl 0383.68058
[21] Păun G.: Marcus’ contextual grammars and languages. A survey. Rev. Roumaine Math. Pures Appl. 24 (1979), 1467-1486. · Zbl 0421.68066
[22] Salomaa A.: Formal languages. Academic Press. New York, Ĩ973. · Zbl 0895.00028
[23] Schmidt J.: Über die Rolle der transfiniten Schlussweisen in einer allgemeinen Idealtheorie. Math. Nachr. 7 (1952), 165-182. · Zbl 0049.16601
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.