Regulated rewriting in formal language theory
Date
2008-03
Authors
Taha, Mohamed A. M. S
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : University of Stellenbosch
Abstract
Context-free grammars are well-studied and well-behaved in terms of decidability, but many
real-world problems cannot be described with context-free grammars. Grammars with regulated
rewriting are grammars with mechanisms to regulate the applications of rules, so that
certain derivations are avoided. Thus, with context-free rules and regulated rewriting mechanisms,
one can often generate languages that are not context-free.
In this thesis we study grammars with regulated rewriting mechanisms. We consider problems
in which context-free grammars are insufficient and in which more descriptive grammars
are required. We compare bag context grammars with other well-known classes of grammars
with regulated rewriting mechanisms. We also discuss the relation between bag context grammars
and recognizing devices such as counter automata and Petri net automata. We show
that regular bag context grammars can generate any recursively enumerable language. We
reformulate the pumping lemma for random permitting context languages with context-free
rules, as introduced by Ewert and Van der Walt, by using the concept of a string homomorphism.
We conclude the thesis with decidability and complexity properties of grammars with
regulated rewriting.
Description
Thesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2008.
Keywords
Regulated rewriting, Formal language theory, Bag context grammars, Dissertations -- Mathematics, Theses -- Mathematics, Formal languages, Rewriting systems (Computer science)