scientific article; zbMATH DE number 3311755

From MaRDI portal
Publication:5592246





Durch die große Bedeutung, die die Theorie der formalen Sprachen sowohl in den Grundlagenuntersuchungen als auch in der mathematischen Kybernetik hat, vermittelt das Buch auf diesem Gebiet für Studenten dieser Disziplinen das notwendige Grundwissen. Es werden erstmalig die wichtigsten Ergebnisse der Theorie der formalen Sprachen in dieser Vollständigkeit dargestellt. Ausgehend von einem allgemeinen Algorithmenbegriff, der etwas zu kurz behandelt wird, werden die einzelnen Grammatiktypen definiert. Zu jedem Sprachtyp werden endliche Automaten ohne Ausgabe angegeben, die genau diese Sprache akzeptieren. Dabei werden verschiedene Automatentypen gegenübergestellt. Besondere Aufmerksamkeit schenken die Verff. den kontextfreien Sprachen, deren Grammatiken in den Normalformen von Chomsky und Greibach dargestellt werden. Ebenso ausführlich sind die Abschnitte über Turing-Maschinen gehalten. In ihnen werden einige Varianten von Turing-Maschinen untersucht und die von diesen akzeptierten Sprachen beschrieben. Wie üblich wird mit Hilfe einer universellen Turing-Maschine die Unentscheidbarkeit des \glqq Halteproblems\grqq{} gezeigt. Davon ausgehend werden für die einzelnen Sprachtypen die Unentscheidbarkeit einiger Eigenschaften (z.B. das Postsche Korrespondenzprinzip) nachgewiesen. Ferner wird untersucht, gegenüber welchen Operationen die Sprachklassen abgeschlossen sind. Vorteilhaft hat sich die parallele Entwicklung der Theorie der formalen Sprachen und der Automatentheorie erwiesen. Damit ist dieses Buch durch seine knappe und übersichtliche Darstellung sehr gut geeignet, das notwendige Grundwissen in der Theorie der formalen Sprachen zu vermitteln. Durch die einfachen, jedoch geschickt gewählten Beispiele werden wichtige Begriffsbildungen hervorgehoben. Besondere Beachtung ist den Übungsaufgaben zu schenken, wobei sich die Verff. bei. einer Neuauflage überlegen sollten, ob es nicht zweckmäßig ist, bei besonders schwierigen Aufgaben am Ende des Buches oder durch entsprechende Literaturhinweise eine Hilfe zu geben. Obwohl dieses Buch leicht verständlich geschrieben ist, ist es zweckmäßig, einige Vorkenntnisse auf den Gebieten Algorithmentheorie und Automatentheorie zu besitzen.





Cited in
(only showing first 100 items - show all)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5592246)