Random generation of finite automata over the domain of the regular languages

[摘要] ENGLISH ABSTRACT: The random generation of finite automata over the domain of their graph structures is a wellknownproblem. However, random generation of finite automata over the domain of the regularlanguages has not been studied in such detail. Random generation algorithms designed for thisdomain would be useful for the investigation of the properties of the regular languages associatedwith the finite automata.We studied the existing enumerations and algorithms to randomly generate UDFAs and binaryDFAs as they pertained to the domain of the regular languages. We evaluated the algorithmsexperimentally across the domain of the regular languages for small values of n and found the distributionsnon-uniform. Therefore, for UDFAs, we derived an algorithm for the random generationof UDFAs over the domain of the regular languages from Domaratzki et. al.'s [9] enumeration ofthe domain of the regular languages. Furthermore, for binary DFAs, we concluded that for largevalues of n, the bijection method is a viable means of randomly generating binary DFAs over thedomain of the regular langagues.We looked at all the random generation of union-UNFAs and-UNFAs across the domain ofthe regular languages. Our study of these UNFAs took all possible variables for the generation ofUNFAs into account. The random generation of UNFAs over the domain of the regular languagesis an open problem

[发布机构] Stellenbosch University