Formale Sprachen

SOMMARIO

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.

ALTRE INFORMAZIONI

• Condizione: Nuovo
• ISBN: 9783540090304
• Dimensioni: 244 x 170 mm Ø 575 gr
• Formato: Brossura
• Illustration Notes: XII, 316 S.
• Pagine Arabe: 316
• Pagine Romane: xii
• Traduttore: Dieterich, E.-W.