Formale Sprachen

InhaltsverzeichnisI. 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.II. Regelsprachen.II. 1 Die Chomsky-Hierarchie.II.2 Der Hierarchie-Nachweis.II.3 Struktursätze.III. Mathematische Maschinen.III. 1 Die Turing-Maschine.III.2 Der linear beschränkte Automat.III.3 Der Kellerautomat.III.4 Der endliche Akzeptor.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.V. Entscheklbarkeit.V.1 Entscheidbare Probleme.V.2 Nichtentscheidbare Probleme.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.