Regulated rewriting in formal language theory

Front Cover
Springer, 1989 - Computers - 308 pages
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.

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Introduction
9
Matrix Programmed and Random Context Grammars
25
Other Grammars with Regulation
95
Copyright

8 other sections not shown

Other editions - View all

Common terms and phrases

Bibliographic information