Random generation of finite automata over the domain of the regular languages
| dc.contributor.advisor | Van Zijl, L. | |
| dc.contributor.author | Raitt, Lesley Anne | |
| dc.contributor.other | Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Institute for Applied Computer Science. | en |
| dc.date.accessioned | 2012-02-08T12:08:44Z | |
| dc.date.available | 2012-02-08T12:08:44Z | |
| dc.date.issued | 2006-12 | |
| dc.description | Thesis (MSc)--University of Stellenbosch, 2007. | en_ZA |
| dc.description.abstract | 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 | en_ZA |
| dc.description.abstract | 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. | af |
| dc.format.extent | vi, 97 leaves : ill. | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/19646 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | |
| dc.rights.holder | Stellenbosch University | en_ZA |
| dc.subject | Sequential machine theory | en_ZA |
| dc.subject | Theses -- Computer science | en_ZA |
| dc.subject | Dissertations -- Computer science | en_ZA |
| dc.title | Random generation of finite automata over the domain of the regular languages | en_ZA |
| dc.type | Thesis | en_ZA |