Dieses Lehrbuch behandelt Schritt fr Schritt alle wichtigen Themen, die Studierende fr Ihren Prfungserfolg bentigen. ber 100 Beispiele, zahlreiche Abbildungen und Hinweise auf beliebte Fehler helfen Ihnen, die Theoretische Informatik zu verstehen und die aufeinander abgestimmten bungsaufgaben zu lsen. Zu allen Aufgaben finden Sie ausfhrliche Musterlsungen.
In jedem der klar und bersichtlich strukturierten Kapitel werden praktische Anwendungen der behandelten Konzepte vorgestellt, die bis in aktuelle Forschungsgebiete der Informatik reichen.
Die 2., vollstndig berarbeitete Auflage enthlt einen neuen und einzigartigen Ansatz zur Darstellung der Berechenbarkeit und Komplexitt, der einen leichteren Zugang zu diesem Thema ermglicht.

Vorwort.- Grundlagen.- Definitionen und Stze.- Aussagenlogik.- Mengen.- Beweistechniken.- Die 0-Notation.- Graphen.- Relationen.- Automaten und formale Sprachen.- Formale Sprachen als Wortmenge.- Kontextfreie Sprachen.- 0L-Systeme.- Typ-0-Sprachen.- Die Chomsky-Hierarchie.- Berechenbarkeit und Komplexitt.- Berechnungsmodelle.- Entscheidbarkeit.- Komplexittstheorie.- Lsungen der Aufgaben.- Anhang.- Index.