scientific article; zbMATH DE number 4003544

From MaRDI portal
Publication:4728260





In the present book, a very important and mathematically interesting topic in formal language theory is presented, namely, the matrix restriction in the derivation of Chomsky grammars. This restriction considerably increases the generative capacity of context-free grammars. Thus the matrix grammars are used in many applications of formal language theory when noncontext-free languages occur and the use of context- sensitive grammars can be avoided. The book consists of two parts. Part one is a monograph devoted to the mathematical theoretic study of matrix grammars and languages. Almost all the known results in this area are presented together with many open problems and conjectures of interest. The second part presents some applications which involve noncontext-free languages and naturally request the use of matrix grammars of various types. Many results are original and some of them were published elsewhere. The large bibliography presented at the end of the book includes referenced papers but also many unreferenced articles about other types of grammars with restrictions in derivation.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4728260)