I. Einführung in die Theorie der formalen Sprachen.- I.1 Natürliche Sprachen.- I.2 Die grundlegenden Definitionen.- I.3 Auswertung arithmetischer Ausdrücke und (kontextfreie) Grammatiken.- I.4 Definition von Programmiersprachen durch kontextfreie Grammatiken.- I.5 Formale Erreichbarkeit von Prozeduren.- I.6 Fragestellungen.- I.6.1 Wort-und Äquivalenzprobleme.- I.6.2 Eindeutigkeit und Mehrdeutigkeit.- I.6.3 Hierarchiefragen und Abschlußeigenschaften.- I.6.4 Mathematische Maschinen und Grammatiken.- I.6.5 Strukturuntersuchungen.- II. Regelsprachen.- II. 1 Die Chomsky-Hierarchie.- II.2 Der Hierarchie-Nachweis.- II.3 Struktursätze.- II.3.1 Die Klasse Ch-1.- II.3.2 Chomsky-reduzierte Grammatiken.- II.3.3 Die Chomsky-Normalform.- II.3.4 Der Satz von Bar'Hillel-Perles-Shamir.- II.3.5 Der Hierarchie-Nachweis.- III. Mathematische Maschinen.- III. 1 Die Turing-Maschine.- III. 1.1 Definition der Turing-Maschine.- III. 1.2 Turing-Maschinen, Regelsysteme und Ch-O-Sprachen.- III.2 Der linear beschränkte Automat.- III.2.1 Der deterministische und der nichtdeterministische linear beschränkte Automat.- III.2.2 dlba, nlba und kontextsensitive Sprachen.- III.3 Der Kellerautomat.- III.3.1 Definition des Automaten.- III.3.2 Kellerautomaten und kontextfreie Sprachen.- III.4 Der endliche Akzeptor.- III.4.1 Definition des endlichen Akzeptors.- IV. Abschlußeigenschaften.- IV. 1 Reguläre Mengen.- IV.2 Der Substitutionssatz.- IV.3 Der Abschluß gegen Durchschnitt und Komplement.- IV.4 Zusammenfassung der Ergebnisse.- IV.5 Automateninduzierte Abbildungen.- IV.5.1 Sequentielle Übersetzer.- IV.5.2 Kellerübersetzer.- V. Entscheklbarkeit.- V.1 Entscheidbare Probleme.- V. 1.1 Das Wortproblem für kontextsensitive Sprachen.- V. 1.2 Das Wortproblem und verwandte Probleme bei kontextfreien Sprachen.- V.1.3 Das Äquivalenzproblem für einseitig lineare Grammatiken.- V.2 Nichtentscheidbare Probleme.- V.2.1 Das Wortproblem für Semi-Thue-Systeme und für Ch-O-Sprachen.- V.2.2 Das Postsche Korrespondenzproblem.- V.2.3 Unentscheidbare Probleme bei kontextfreien Grammatiken.- V.2.4 Zwei nichtentscheidbare Probleme bei kontextsensitiven Grammatiken.- VI. Eindeutigkeit.- VI.1 Die Problemstellung.- VI.2 Formalisierung des Ableitungsprozesses.- VI.3 Nicht wesentlich verschiedene Ableitungen.- VI.4 Veranschaulichung durch Bäume.- VI.5 Weitere Eigenschaften der Relation "?".- VI.6 Eindeutige Grammatiken und eindeutige Sprachen.- VI.7 Inhärente Mehrdeutigkeit.- VII. Eine Einführung in die syntaktische Analyse.- VII.1 Die Problemstellung.- VII.2 Ein Turingmaschinenmodell zur Syntaxanalyse.- VII.3 Die Greibach-Normalform.- VII.4 Die "schwierigste" kontextfreie Sprache.- VII.5 Der Satz von Chomsky-Schützenberger.- Lösungen der Übungsaufgaben.- Symbole und Bezeichnungen.- Stichwortverzeichnis.