Automaten, Sprachen, Berechenbarkeit

Der Begriff der formalen Sprache ist essenziell für viele Bereiche der Informatik, einschließlich Programmiersprachen, Compilerbau und Datenbanktechnologie. Anhand motivierender Beispiele werden klassische Systeme formaler Sprachen untersucht, wobei die Hierarchie der Automaten – von endlichen Automaten über Kellerautomaten bis zu Turing-Maschinen – und die Hierarchie der Chomsky-Grammatiken gegenübergestellt werden. Die verschiedenen Sprachklassen werden diskutiert und klar voneinander abgegrenzt. Zudem werden grundlegende Begriffe wie „Algorithmus“, „Berechenbarkeit“ und „Entscheidbarkeit“ behandelt, wobei deren Bedeutung für die Informatik und die Theorie formaler Sprachen hervorgehoben wird. Ziel ist es, eine leicht verständliche und präzise Einführung in diese wichtigen Bereiche der Informatik zu bieten. Besonders soll ein Verständnis für methodische Grundlagen, beispielsweise die Konzepte von Programmiersprachen, gefördert werden. Das Buch ist Teil des MeDoc-Projektes und in der elektronischen Informatik-Bibliothek verfügbar, weiterhin zugänglich über das InterDoc-Projekt.