Regulated rewriting in formal language theory

Simple item page
dc.contributor.advisorVan der Merwe, A. B.
dc.contributor.authorTaha, Mohamed A. M. Sen_ZA
dc.contributor.otherUniversity of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences.
dc.date.accessioned2008-06-23T12:40:27Zen_ZA
dc.date.accessioned2010-06-01T08:28:22Z
dc.date.available2008-06-23T12:40:27Zen_ZA
dc.date.available2010-06-01T08:28:22Z
dc.date.issued2008-03en_ZA
dc.descriptionThesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2008.
dc.description.abstractContext-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.en_ZA
dc.identifier.urihttp://hdl.handle.net/10019.1/1600
dc.language.isoenen_ZA
dc.publisherStellenbosch : University of Stellenbosch
dc.rights.holderUniversity of Stellenbosch
dc.subjectRegulated rewritingen_ZA
dc.subjectFormal language theoryen_ZA
dc.subjectBag context grammarsen_ZA
dc.subjectDissertations -- Mathematicsen
dc.subjectTheses -- Mathematicsen
dc.subjectFormal languagesen
dc.subjectRewriting systems (Computer science)en
dc.subject.otherMathematical Sciencesen_ZA
dc.subject.otherMathematicsen_ZA
dc.titleRegulated rewriting in formal language theoryen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
taha_regulated_2008.pdf
Size:
685.06 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters Degrees (Mathematical Sciences)