"Automatentheorie und formale Sprachen 002.ps.gz" - читать интересную книгу автораAutomatentheorie und formale Sprachen I Rudolf Beyer WS 91 / 92 Literatur 1) John E. Hopcroft Jeffrey D. Ullman: Einf"uhrung in die Automatentheorie, formale Sprachen und Komplexit"atstheorie; Addison-Wesley, Bonn 19892) H. Maurer, W. Bucher: Theoretische Grundlagen der Programmiersprachen; Automaten und Sprachen; BI, Mannheim 1984 3) A. V. Aho, Vol. I; Prentice-Hall, Englewood Cliffs, New Jersey 19724) A.K. Salomaa: Formale Sprachen; Springer, Berlin 1978 1 Inhaltsverzeichnis 1 Einf"uhrung 4 1.1 Grundlegende Begriffe : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.2 Themenstellung : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 2 Endliche Automaten und regul"are Ausdr"ucke 10 2.1 Systeme mit endlicher Zustandsmenge : : : : : : : : : : : : : : : : : 10 2.2 Deterministische endliche Automaten : : : : : : : : : : : : : : : : : : 11 2.3 Nichtdeterministische endliche Automaten : : : : : : : : : : : : : : : 14 2.4 Endliche Automaten mit ffl- "Uberg"angen : : : : : : : : : : : : : : : : : 21 2.5 Regul"are Ausdr"ucke : : : : : : : : : : : : : : : : : : : : : : : : : : : 26 2.6 Weitere Verallgemeinerungen : : : : : : : : : : : : : : : : : : : : : : 35 2.6.1 Nichtdeterministische Rabin - Scott - Automaten : : : : : : : 35 2.6.2 Zweiseitige deterministische endliche Automaten : : : : : : : 35 2.7 Endliche Automaten mit Ausgabe : : : : : : : : : : : : : : : : : : : 36 2.8 Anwendungen f"ur endliche Automaten : : : : : : : : : : : : : : : : : 39 3 Eigenschaften von regul"aren Mengen 43 3.1 Das Pumping-Lemma f"ur regul"are Mengen : : : : : : : : : : : : : : : 43 3.2 Abgeschlossenheitseigenschaften regul"arer Mengen : : : : : : : : : : 45 3.3 Entscheidungsalgorithmen f"ur regul"are Mengen : : : : : : : : : : : : 52 3.4 Der Minimalautomat : : : : : : : : : : : : : : : : : : : : : : : : : : : 54 |
|
|