Random generation of finite automata over the domain of the regular languages
Date
2006-12
Authors
Raitt, Lesley Anne
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
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
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.
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.
Description
Thesis (MSc)--University of Stellenbosch, 2007.
Keywords
Sequential machine theory, Theses -- Computer science, Dissertations -- Computer science