Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Random generation of finite automata over the domain of the regular languages
Thesis (MSc)--University of Stellenbosch, 2007.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2012
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614093514375168 |
|---|---|
| access_status_str | Open Access |
| author | Raitt, Lesley Anne |
| author2 | Van Zijl, L. |
| author_browse | Raitt, Lesley Anne Van Zijl, L. |
| author_facet | Van Zijl, L. Raitt, Lesley Anne |
| author_sort | Raitt, Lesley Anne |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--University of Stellenbosch, 2007. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/19646 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:46:33.531Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2012 |
| publishDateRange | 2012 |
| publishDateSort | 2012 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/19646 Random generation of finite automata over the domain of the regular languages Raitt, Lesley Anne Van Zijl, L. Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Institute for Applied Computer Science. Sequential machine theory Theses -- Computer science Dissertations -- Computer science Thesis (MSc)--University of Stellenbosch, 2007. ENGLISH ABSTRACT: The random generation of finite automata over the domain of their graph structures is a wellknown problem. However, random generation of finite automata over the domain of the regular languages has not been studied in such detail. Random generation algorithms designed for this domain would be useful for the investigation of the properties of the regular languages associated with the finite automata. We studied the existing enumerations and algorithms to randomly generate UDFAs and binary DFAs as they pertained to the domain of the regular languages. We evaluated the algorithms experimentally across the domain of the regular languages for small values of n and found the distributions non-uniform. Therefore, for UDFAs, we derived an algorithm for the random generation of UDFAs over the domain of the regular languages from Domaratzki et. al.’s [9] enumeration of the domain of the regular languages. Furthermore, for binary DFAs, we concluded that for large values of n, the bijection method is a viable means of randomly generating binary DFAs over the domain of the regular langagues. We looked at all the random generation of union-UNFAs and -UNFAs across the domain of the regular languages. Our study of these UNFAs took all possible variables for the generation of UNFAs into account. The random generation of UNFAs over the domain of the regular languages is an open problem AFRIKAANSE OPSOMMING: Die ewekansige generasie van eindige toestand outomate (eto’s) oor die domein van hul grafiekstrukture is ’n bekende probleem. Nieteenstaande het die ewekansige generasie van eindige toestand outomate oor die domein van die regulˆere tale nie soveel aandag gekry nie. Algoritmes wat eindige toestand outomate ewekansig genereer oor die domein van die regulˆere tale sal nuttig wees om die ondersoek van die eienskappe van regulˆere tale, wat met eto’s verbind is, te bewerkstellig. Ons het die bestaande aftellings en algoritmes bestudeer vir die ewekansige generasie van deterministiese eindige toestand outomate (deto’s) met een en twee alfabetiese simbole soos dit betrekking het op die domein van die regulˆere tale bestudeer. Ons het die algoritmes eksperimenteel beoordeel oor die domein van die regulˆere tale vir outomate met min toestande en bevind dat die verspreiding nie eenvomig is nie. Daarom het ons ’n algoritme afgelei vir die ewekansige generasie van deto’s met een alfabetsimbool oor die domein van die regulˆere tale van Domaratzki et. al. [9] se aftelling. Bowendien, in die geval van deto’s met twee alfabetsimbole met ’n groot hoeveelheid toestande is die ‘bijeksie metode ’n goeie algoritme om te gebruik vir die ewekansige generasie van hierdie deto’s oor die domein van die regulˆere tale. Ons het ook die ewekansige generasie van [-nie-deterministiese eindige toestand outomate en -nie-deterministiese eindige toestand outomate oor die domein van die regulˆere tale bestudeer. Ons studie van hierdie neto’s het alle moontlike veranderlikes in ageneem. Die ewekansige generering van deto’s oor die domein van die regulˆere tale is ’n ope probleem. 2012-02-08T12:08:44Z 2012-02-08T12:08:44Z 2006-12 Thesis http://hdl.handle.net/10019.1/19646 en_ZA Stellenbosch University vi, 97 leaves : ill. application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Sequential machine theory Theses -- Computer science Dissertations -- Computer science Raitt, Lesley Anne Random generation of finite automata over the domain of the regular languages |
| title | Random generation of finite automata over the domain of the regular languages |
| title_full | Random generation of finite automata over the domain of the regular languages |
| title_fullStr | Random generation of finite automata over the domain of the regular languages |
| title_full_unstemmed | Random generation of finite automata over the domain of the regular languages |
| title_short | Random generation of finite automata over the domain of the regular languages |
| title_sort | random generation of finite automata over the domain of the regular languages |
| topic | Sequential machine theory Theses -- Computer science Dissertations -- Computer science |
| url | http://hdl.handle.net/10019.1/19646 |
| work_keys_str_mv | AT raittlesleyanne randomgenerationoffiniteautomataoverthedomainoftheregularlanguages |