Diese Einführung umfasst die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und einen Überblick über die Komplexitätstheorie. Alle Beweise werden ausführlich behandelt. Schwierige Beweise werden nicht etwa abgekürzt, sondern eingehender behandelt. Damit bietet dieses Buch zugleich eine Einführung in die Technik des Beweisens und ist somit sowohl für Anfänger als auch Dozenten geeignet. Ein größeres Kapitel behandelt alternative Rechenmodelle, unter anderem Zwei-Register-Maschinen, Tag-Systeme, Wang-Maschinen, Rödding-Netze, Splicing und reversible Rechnungen.
Author(s): Dr. Katrin Erk, Prof. Dr. Lutz Priese (auth.)
Series: eXamen.press
Edition: 3
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2008
Language: German
Pages: 485
Tags: Mathematical Logic and Formal Languages; Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Mathematics of Computing; Mathematical Logic and Foundations; Combinatorics
Front Matter....Pages I-XV
Einleitung....Pages 1-1
Begriffe und Notationen....Pages 3-34
Eine kurze Einführung in die Aussagenlogik....Pages 35-49
Front Matter....Pages 51-51
Grammatiken und formale Sprachen....Pages 53-61
Reguläre Sprachen und endliche Automaten....Pages 63-107
Kontextfreie Sprachen....Pages 109-163
Turing-Maschinen....Pages 165-193
Die Sprachklassen $$ \mathcal{L},\mathcal{L}_0 $$ und $$ \mathcal{L}_1 $$ ....Pages 195-214
Abschlußeigenschaften von Sprachklassen....Pages 215-223
Front Matter....Pages 225-225
Einleitung....Pages 227-231
Registermaschinen....Pages 233-251
Rekursive Funktionen....Pages 253-289
Unentscheidbare Probleme....Pages 291-325
Alternative Berechnungsmodelle....Pages 327-437
Komplexität....Pages 439-472
Back Matter....Pages 473-485
