Regulated rewriting in formal language theory
It is well-known that context-free grammars cannot cover all aspects of natural languages, progamming languages and other related fields. Therefore a lot of mechanisms have been introduced which control the application of context-free rules. This book presents 25 different regulating mechanisms by definitions, examples and basic facts, especially concerning hierarchies. Matrix, programmed, and random context grammars as typical representants are studied in more detail. Besides their algebraic and decidability properties a comparison is made with respect to syntactic complexity measures and pure versions. Further topics are combinations of some control mechanisms, regulated L systems, automata characterizations, Szilard languages, and grammar forms of regulated grammars as well as selective substitution grammars as one common generalization.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Matrix Programmed and Random Context Grammars
Other Grammars with Regulation
8 other sections not shown
Other editions - View all
A-free A-rules alphabet appearance checking application arbitrary Clearly construct contains context-free grammar context-free languages context-sensitive context-sensitive grammars context-sensitive language core productions current string Dassow defined Definition denote the family derivation in G EDTOL erasing rules ETOL Example family of languages form F grammar G grammars with appearance Hence homomorphisms inclusion indexed grammar Indian parallel integer introduce Jf SM Jf(CF Jf(CS Jf(M Jf(RC Jf(SM Kuroda normal form label language L(0 leftmost derivations Let G letter linear matrix grammar form non-context-free nonterminals normal form obtain occurrences Open problems parallel grammar Paun proof of Lemma prove random context grammar regular language regulated grammars regulated rewriting replace rewritten Rozenberg Russian parallel scattered context grammar selective substitution grammar selector language semilinear sentential form simple matrix grammar simulated terminating derivation Theorem TOL language TOL system unordered valence grammar word