Formale Sprachen

In diesem Buch wird eine Theorie der formalen Sprachen yom Standpunkt der Erzeugungsverfahren, hauptslichlich der Gramma­ tiken aus entwickelt. Erkennungsverfahren, also Automaten, wer­ den nur als eine zweite Moglichkeit eingefiihrt und im Rahmen von Ersetzungssystemen vorgestellt. Das Hauptgewicht liegt auf den mathematischen Aspekten der formalen Sprachen und nicht auf ihren Anwendungen. Wer nur an Anwendungen aufProgrammiersprachen (bzw. narurliche Spra­ chen) interessiert ist, wiirde sicherlich eine ausfiihrlichere Diskus­ sion von Themen wie LR(k)-Grammatiken (bzw. Transformations­ grammatiken) bevorzugen. So1che Diskussionen liegen au~erhalb des Rahmens dieses Buches. Wir vermeiden unnotige Abstraktionen, da von Seiten des Lesers keine tieferen mathematischen Kenntnisse verlangt werden. Es wird nur vorausgesetzt, d~ der Leser mit den grundlegendsten Begriffen der Algebra und der Logik vertraut ist. Es sind keine Vorkenntnisse tiber formale Sprachen erforderlich. Das Niveau der Darstellung entspricht dem Stoffkurz nach dem Vordiplom. Das Buch ist in sich abgeschlossen, so d~ man keine weiteren Quellen fUr die Beweise von Ergebnissen benotigt, die als Slitze formuliert sind. Einige weitere Ergebnisse werden bisweilen ohne Beweis angefiihrt, hauptslichlich als Behauptungen oder in den Be­ merkungen im Anschl~ an einige Abschnitte. Selbstverstandlich werden diese Ergebnisse in den Beweisen spliterer Slitze nicht ver­ wendet. Es wurde auch versucht, die jiingsten Ergebnisse mit ein­ zubeziehen. Danksagungen Teile des Manuskriptes flir dieses Buch wurden als Unterlagen fUr Vorlesungen verwendet, die an den Universitaten von Aarhus (Danemark), Turku (Finnland), Uppsala (Schweden) und Western Ontario (London, Canada) gehalten wurden. Ich mochte den Teil­ nehmern dieser VorleSlingen danken.