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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/19646 |
| Date | 12 1900 |
| Creators | Raitt, Lesley Anne |
| Contributors | Van Zijl, L., Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Institute for Applied Computer Science. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | Unknown |
| Type | Thesis |
| Format | vi, 97 leaves : ill. |
| Rights | Stellenbosch University |
Page generated in 0.0038 seconds