Titelaufnahme

Titel
Abzählung von Automaten, formalen Sprachen und verwandten Strukturen / Georg Sedlitz
Weitere Titel
Enumeration of automata, formal languages and related structures
VerfasserSedlitz, Georg
Begutachter / BegutachterinGittenberger, Bernhard
ErschienenWien, 2017
Umfang109 Seiten : Illustrationen
HochschulschriftTechnische Universität Wien, Diplomarbeit, 2017
Anmerkung
Text in englischer Sprache
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (EN)regular languages / finite automata / asymptotic enumeration / Boltzmann sampling
URNurn:nbn:at:at-ubtuw:1-99595 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Abzählung von Automaten, formalen Sprachen und verwandten Strukturen [1.65 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Englisch)

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.