Formale Sprachen

ISBN-13: 9783540090304 / Niemiecki / Miękka / 1978 / 316 str.

Arto K. Salomaa; E. -W Dieterich

Opis

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."

Spis treści

Eins.- I. Sprache und Grammatik.- 1. Ersetzungssysteme.- 2. Grammatiken.- 3. Abgeschlossenheit bezüglich elementarer Operationen.- 4. Automatenhierarchie.- Übungen.- Bibliographische Bemerkungen.- Bibliographie.- II. Reguläre und kontextfreie Sprachen.- 5. Äquivalente Charakterisierungen regulärer Sprachen.- 6. Kontextfreie Ableitungen.- 7. Parikh-Abbildung und homomorphe Charakterisierung.- 8. Teilfamilien kontextfreier Sprachen.- Übungen.- Bibliographische Bemerkungen.- Bibliographie.- III. Kontext-sensitive Sprachen und Typ-O-Sprachen.- 9. Rekursiv aufzählbare und rekursive Sprachen. Hierarchie von vier Sprachfamilien.- 10. Platzbedarf.- 11. Homomorphe Charakterisierung von Typ-O-Sprachen.- 12. Rudimentäre Prädikate.- Übungen.- Bibliographische Bemerkungen.- Bibliographie.- Zwei.- IV. Abstrakte Familien von Sprachen.- 1. Abhängigkeit von Operationen.- 2. AFL’s und verwandte Systeme.- Übungen.- Bibliographische Bemerkungen.- Bibliographie.- V. Gesteuerte Ersetzung.- 3. Matrix-Grammatiken.- 4. Zeitvariierende Grammatiken.- 5. Programmierte Grammatiken.- 6. Kontrollsprachen.- 7. Geordnete Grammatiken.- Übungen.- Bibliographische Bemerkungen.- Bibliographie.- VI. Kontextfreie Sprachen, Fortsetzung.- 8. Formale Potenzreihen.- 9. Mehrdeutigkeit.- 10. Eingeschränkte Ableitungen.- 11. Regulärartige Ausdrücke.- 12. LR(k)- und LL(k)-Grammatiken.- Übungen.- Bibliographische Bemerkungen.- Bibliographie.- VII. Weitere Klassen von Erzeugungsverfahren.- 13. Lindenmayer-Systeme: Parallele Ersetzung ohne terminale Zeichen.- 14. Transformationsgrammatiken,kategorische, indizierte, Scattered-Kontext- und probabüistische Grammatiken.- Übungen.- Bibliographische Bemerkungen.- Bibliographie.- Drei.- VIII. Lösbarkeit und Unlösbarkeit.- 1. Die Existenz von Algorithmen.- 2. Das Postsche Korrespondenzproblem und unlösbare Probleme für Sprachen.- 3. Lösbarkeit der Strukturäquivalenz kontextfreier Grammatiken.- Übungen.- Bibliographische Bemerkungen.- Bibliographie.- IX. Komplexität.- 4. Zeitbeschränkte Grammatiken. Der Beschleunigungssatz.- 5. Axiomatischer Ansatz. Das Gap-Theorem.- Übungen.- Bibliographische Bemerkungen.- Bibliographie.- Einführung in die Literatur.