Formale Sprachen

Inhaltsverzeichnis I. Einführung in die Theorie der formalen Sprachen. I.1 Natürliche Sprachen. I.2 Grundlegende 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. II. Regelsprachen. II.1 Chomsky-Hierarchie. II.2 Hierarchie-Nachweis. II.3 Struktursätze. III. Mathematische Maschinen. III.1 Turing-Maschine. III.2 Linear beschränkter Automat. III.3 Kellerautomat. III.4 Endlicher Akzeptor. IV. Abschlußeigenschaften. IV.1 Reguläre Mengen. IV.2 Substitutionssatz. IV.3 Abschluß gegen Durchschnitt und Komplement. IV.4 Zusammenfassung der Ergebnisse. IV.5 Automateninduzierte Abbildungen. V. Entscheidbarkeit. V.1 Entscheidbare Probleme. V.2 Nichtentscheidbare Probleme. VI. Eindeutigkeit. VI.1 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 Sprachen. VI.7 Inhärente Mehrdeutigkeit. VII. Einführung in die syntaktische Analyse. VII.1 Problemstellung. VII.2 Turingmaschinenmodell zur Syntaxanalyse. VII.3 Greibach-Normalform. VII.4 Schwierigste kontextfreie Sprache. VII.5 Satz von Chomsky-Schützenberger. Lösungen der Übungsaufgaben. Symbole und Bezeichnungen. Stichwortverzeichnis.