Einführung in die Automatentheorie

Das vorliegende Buch ist aus Vorlesungen entstanden, die sich an Mathematiker, Informatiker und Naturwissenschaftler gewandt haben. Das Buch eignet sich - da es sich urn eine einftihrende Darstellung handelt - jedoch auch ftir Ingenieure, insbesondere fur Nachrichtentechniker mit vertieftem Interesse an Fragen der Nachrichtentheorie. Fur einige Hinweise bin ich Fraulein Dr. I. Bruckner und Herrn Dipl. -Math. W. Thomas zu Dank verpflichtet. Auf Herrn Dipl. -Math. H. Volker gehen einige durchgeftihrte Beispiele zuruck. Herrn Dr. W. Brakemeier danke ich ftir seine Mithilfe beim Lesen der Korrekturen. Ganz besonders herzlich danke ich Frau G. Krtiese ftir die Herstellung eines Teils der Reinschrift des Manuskriptes. Dem Vieweg-Verlag mochte ich fUr die Aufnahme des Bandchens in die Reihe un i-text danken. Hamburg, im Oktober 1976 H. H. Homuth IV Inhaltsverzeichnis Einleitung V 1. Grundlagen 1 1. 1. Alphabete, Warter, Wortmengen 1. 2. Determinierte Automaten 7 1. 3. Verallgemeinerungen 12 1. 4. Algebraische Automaten 15 Allgemeine Automaten 2. 18 Xquivalenz und Reduktion von Automaten 2. 1. 18 Zusammenhangsbegriffe bei Automaten 2. 2. 27 Homomorphie und Isomorphie bei Automaten 2. 3. 31 3. Wortfunktionen 37 Grundlegende Begriffe 3. 1. 37 Darstellbarkeit von Abbildungen in Automaten 3. 2. 39 Realisierung von Wortfunktionen 3. 3. 45 3. 4. Ereignisse 52 3. 5. ReguHire Ereignisse 56 4. Uber Automaten mit speziellen Uberfiihrungs-und Ergebnisfunktionen 63 5. Lineare Automaten 73 Allgemeines 5. 1. 73 Reduktion linearer Automaten 5. 2. 79 6. Boolesche Automaten 86 Grundlagen 6. 1. 86 Lineare Boolesche Automaten 6. 2. 96 Anwendungen 6. 3.