Read more
In diesem Buch wird eine Theorie der formalen Sprachen yom Standpunkt der Erzeugungsverfahren, hauptslichlich der Gramma tiken aus entwickelt. Erkennungsverfahren, also Automaten, wer den nur als eine zweite Moglichkeit eingefiihrt und im Rahmen von Ersetzungssystemen vorgestellt. Das Hauptgewicht liegt auf den mathematischen Aspekten der formalen Sprachen und nicht auf ihren Anwendungen. Wer nur an Anwendungen aufProgrammiersprachen (bzw. narurliche Spra chen) interessiert ist, wiirde sicherlich eine ausfiihrlichere Diskus sion von Themen wie LR(k)-Grammatiken (bzw. Transformations grammatiken) bevorzugen. So1che Diskussionen liegen au~erhalb des Rahmens dieses Buches. Wir vermeiden unnotige Abstraktionen, da von Seiten des Lesers keine tieferen mathematischen Kenntnisse verlangt werden. Es wird nur vorausgesetzt, d~ der Leser mit den grundlegendsten Begriffen der Algebra und der Logik vertraut ist. Es sind keine Vorkenntnisse tiber formale Sprachen erforderlich. Das Niveau der Darstellung entspricht dem Stoffkurz nach dem Vordiplom. Das Buch ist in sich abgeschlossen, so d~ man keine weiteren Quellen fUr die Beweise von Ergebnissen benotigt, die als Slitze formuliert sind. Einige weitere Ergebnisse werden bisweilen ohne Beweis angefiihrt, hauptslichlich als Behauptungen oder in den Be merkungen im Anschl~ an einige Abschnitte. Selbstverstandlich werden diese Ergebnisse in den Beweisen spliterer Slitze nicht ver wendet. Es wurde auch versucht, die jiingsten Ergebnisse mit ein zubeziehen. Danksagungen Teile des Manuskriptes flir dieses Buch wurden als Unterlagen fUr Vorlesungen verwendet, die an den Universitaten von Aarhus (Danemark), Turku (Finnland), Uppsala (Schweden) und Western Ontario (London, Canada) gehalten wurden. Ich mochte den Teil nehmern dieser VorleSlingen danken.
List of contents
Eins.- I. Sprache und Grammatik.- II. Reguläre und kontextfreie Sprachen.- III. Kontext-sensitive Sprachen und Typ-O-Sprachen.- Zwei.- IV. Abstrakte Familien von Sprachen.- V. Gesteuerte Ersetzung.- VI. Kontextfreie Sprachen, Fortsetzung.- VII. Weitere Klassen von Erzeugungsverfahren.- Drei.- VIII. Lösbarkeit und Unlösbarkeit.- IX. Komplexität.- Einführung in die Literatur.
