Willkommen, schön sind Sie da!
Logo Ex Libris

Formale Sprachen

  • Kartonierter Einband
  • 332 Seiten
In diesem Buch wird eine Theorie der formalen Sprachen yom Standpunkt der Erzeugungsverfahren, hauptslichlich der Gramma­ tiken a... Weiterlesen
20%
77.00 CHF 61.60
Print on demand - Exemplar wird für Sie besorgt.

Beschreibung

Klappentext

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.



Inhalt

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.

Produktinformationen

Titel: Formale Sprachen
Autor:
Übersetzer:
EAN: 9783540090304
ISBN: 978-3-540-09030-4
Format: Kartonierter Einband
Herausgeber: Springer Berlin Heidelberg
Genre: Allgemeines & Lexika
Anzahl Seiten: 332
Gewicht: 540g
Größe: H200mm x B250mm x T20mm
Jahr: 1978
Zuletzt angesehen
Verlauf löschen