Diese Einführung zeichnet sich durch Verständlichkeit und gute Lesbarkeit aus. Sie umfaßt die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und einen Überblick über die Komplexitätstheorie. Das Buch eignet sich insbesondere für Anfänger, da alle Beweise im Detail ausgeführt sind. Damit bietet es gleichzeitig eine Einführung in die Technik des Beweisens. Für Dozenten ist interessant, daß die Beweise nicht nur wie vielfach üblich skizziert sind und auch Nicht-Standard-Berechnungsmodelle vorgestellt werden.
Reihe
Sprache
Verlagsort
Verlagsgruppe
Illustrationen
1
1 s/w Abbildung
X, 433 S. 1 Abb.
Dateigröße
ISBN-13
978-3-662-10429-3 (9783662104293)
DOI
10.1007/978-3-662-10429-3
Schweitzer Klassifikation
1. Einleitung.- 2. Begriffe und Notationen.- 3. Eine kurze Einführung in die Aussagenlogik.- I. Formale Sprachen.- 4. Grammatiken und formale Sprachen.- 5. Reguläre Sprachen und endliche Automaten.- 6. Kontextfreie Sprachen.- 7. Turing-Maschinen.- 8. Die Sprachklassen ?, ?0 und ?1.- 9. Abschlußeigenschaften von Sprachklassen.- II. Berechenbarkeit.- 10. Einleitung.- 11. Registermaschinen.- 12. Rekursive Funktionen.- 13. Unentscheidbare Probleme.- 14. Alternative Berechnungsmodelle.- 15. Komplexität.- Bibliographische Hinweise.
