Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Regulated rewriting in formal language theory
Thesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2008.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Stellenbosch : University of Stellenbosch
2008
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613785021218816 |
|---|---|
| access_status_str | Open Access |
| author | Taha, Mohamed A. M. S |
| author2 | Van der Merwe, A. B. |
| author_browse | Taha, Mohamed A. M. S Van der Merwe, A. B. |
| author_facet | Van der Merwe, A. B. Taha, Mohamed A. M. S |
| author_sort | Taha, Mohamed A. M. S |
| collection | Thesis |
| dc_rights_str_mv | University of Stellenbosch |
| description | Thesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2008. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/1600 |
| institution | Stellenbosch University (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:41:39.515Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2008 |
| publishDateRange | 2008 |
| publishDateSort | 2008 |
| publisher | Stellenbosch : University of Stellenbosch |
| publisherStr | Stellenbosch : University of Stellenbosch |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/1600 Regulated rewriting in formal language theory Taha, Mohamed A. M. S Van der Merwe, A. B. University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Regulated rewriting Formal language theory Bag context grammars Dissertations -- Mathematics Theses -- Mathematics Formal languages Rewriting systems (Computer science) Mathematical Sciences Mathematics Thesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2008. 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. 2008-06-23T12:40:27Z 2010-06-01T08:28:22Z 2008-06-23T12:40:27Z 2010-06-01T08:28:22Z 2008-03 Thesis http://hdl.handle.net/10019.1/1600 en University of Stellenbosch application/pdf Stellenbosch : University of Stellenbosch |
| spellingShingle | Regulated rewriting Formal language theory Bag context grammars Dissertations -- Mathematics Theses -- Mathematics Formal languages Rewriting systems (Computer science) Mathematical Sciences Mathematics Taha, Mohamed A. M. S Regulated rewriting in formal language theory |
| title | Regulated rewriting in formal language theory |
| title_full | Regulated rewriting in formal language theory |
| title_fullStr | Regulated rewriting in formal language theory |
| title_full_unstemmed | Regulated rewriting in formal language theory |
| title_short | Regulated rewriting in formal language theory |
| title_sort | regulated rewriting in formal language theory |
| topic | Regulated rewriting Formal language theory Bag context grammars Dissertations -- Mathematics Theses -- Mathematics Formal languages Rewriting systems (Computer science) Mathematical Sciences Mathematics |
| url | http://hdl.handle.net/10019.1/1600 |
| work_keys_str_mv | AT tahamohamedams regulatedrewritinginformallanguagetheory |