Bibliographic Metadata

Title
Abzählung von Automaten, formalen Sprachen und verwandten Strukturen / Georg Sedlitz
Additional Titles
Enumeration of automata, formal languages and related structures
AuthorSedlitz, Georg
CensorGittenberger, Bernhard
PublishedWien, 2017
Description109 Seiten : Illustrationen
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2017
Annotation
Text in englischer Sprache
LanguageEnglish
Document typeThesis (Diplom)
Keywords (EN)regular languages / finite automata / asymptotic enumeration / Boltzmann sampling
URNurn:nbn:at:at-ubtuw:1-99595 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Abzählung von Automaten, formalen Sprachen und verwandten Strukturen [1.65 mb]
Links
Reference
Classification
Abstract (English)

One way of characterizing regular languages is through finite deterministic or nondeterministic automata. A counting sequence can be obtained by considering automata with n states over an input alphabet of size k. We study the asymptotic behaviour of this sequence for different classes of automata and their relations to other structures. Upper and lower bounds are obtained for the number of automata and the number of accepted languages using a variety of methods ranging from number theory and graph theory to complex analysis. Furthermore, we will introduce a method of random smpling for initially connected automata.

Stats
The PDF-Document has been downloaded 31 times.