Übungsbuch Automaten und formale Sprachen

117 Aufgaben und Lösungen

verfasst von: Stefan O. Knapp

Verlag: Springer Fachmedien Wiesbaden

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Die theoretische Informatik ist – wie der Namen schon sagt – ein höchst abstraktes Teilgebiet der Informatik. Die Übungen in diesem Buch ermöglichen Schülern und Studierenden einen leichteren Zugang zu dem vielschichtigen Themenkomplex "Automaten und formalen Sprachen". Denn "träges", hoch theoretisches Wissen lässt sich oft erst durch praktische Anwendung meistern. Dieses praktische Übungsbuch beinhaltet 117 Aufgaben zu folgenden Themen:
- endlichen Automaten- Grammatiken- Kellerautomaten- regulären Ausdrücken und regulären Sprachen
Alle Übungen in diesem Buch sind darauf ausgelegt, die theoretischen Inhalte zu erproben und zu vertiefen. Die Aufgabenstellungen und die Lösungen werden Schritt für Schritt und durch viele Abbildungen anschaulich gemacht. Dabei sind sämtliche Lösungen detailliert ausgearbeitet und zeigen leicht nachvollziehbare Lösungswege. Doch der Autor geht sogar noch über die konkrete Einübung des Lernstoffs hinaus. Seine Übungen schulen die Leser überdies in wichtigen anderen Fähigkeiten (wie Zeitmanagement, Motivation und Konzentration), die ebenfalls entscheidend für den Prüfungserfolg sein können.
Damit ist das Übungsbuch ein idealer Begleiter für alle Schüler und Studierende, die sich effektiv auf Klausuren und Prüfungen vorbereiten möchten. Der Band richtet sich insbesondere an Studierende der Informatik, Mathematik, Informationstechnologie, Elektro- und Medientechnik und an Schüler in der gymnasialen Oberstufe und ihre Lehrer und Dozenten.

Inhaltsverzeichnis

Frontmatter

Endliche Automaten

Zusammenfassung

Endliche Automaten sind theoretische Zustandsmaschinen, die einfache Entscheidungsprobleme lösen können. D. h., mit ihrer Hilfe kann eine Teilklasse von Algorithmen bzw. Programmen formal beschrieben und untersucht werden. Konkret beschreiben endliche Automaten die Sprachklasse der regulären Sprachen. Dementsprechend behandeln die 54 Aufgaben zu endlichen Automaten Zusammenhänge zwischen Automatenmodellen und regulären Sprachen, wobei zentrale Elemente

die Automatenkonstruktion und -transformation,
Überführung von Transitionstabellen in Transitionsdiagramme,
Zusammenhänge zwischen regulären Grammatiken und endlichen Automaten sowie
reguläre Ausdrücke als alternative Darstellungsform zu von endlichen Automaten akzeptierten Sprachen

sind. Lernziele sind demnach die Einordnung von endlichen Automaten als Darstellungsform für reguläre Sprachen, die Übung beim Operieren mit endlichen Automaten und ein beschleunigter Erkenntnisgewinn durch Transfer, Wiederholung und Vertiefung der Automatentheorie.

Stefan O. Knapp

Grammatiken

Zusammenfassung

Grammatiken bilden den Schnittpunkt zwischen Linguistik und Informatik und stellen neben den endlichen Automaten eine weitere Möglichkeit zur eindeutigen Beschreibung von Sprachen dar. Grammatiken geben Regeln vor, nach denen eine Sprache aufgebaut ist bzw. Wörter einer Sprache erzeugt werden. Ihr Funktionsprinzip ist ein Ersetzungsmechanismus: Ausgehend von einem Startsymbol wird durch Ersetzungen Schritt für Schritt ein Wort gebildet, das einer Sprache, die durch eine Grammatik definiert ist, zugehörig ist. Im Gegensatz zu endlichen Automaten können Grammatiken nicht nur reguläre Sprachen, sondern auch Sprachen aus anderen Chomsky-Sprachklassen beschreiben.

Die 39 vorliegenden Aufgaben behandeln

Zusammenhänge zwischen Sprachklassen und Grammatiktypen
die Konstruktion von Grammatiken und die Prüfung von Wörtern hinsichtlich ihrer Erzeugbarkeit,
die Transformation von Grammatiken nach bestimmten Regeln (z. B. Reduktion, ϵ-Befreiung) sowie
alternative Darstellungsformen für von Grammatiken erzeugte Wörter bzw. Sprachen (Bäume, Diagramme).

Stefan O. Knapp

Kellerautomaten

Zusammenfassung

Das Prinzip von Kellerautomaten ähnelt bezüglich Eingabemechanismus dem der endlichen Automaten (Lesen vom Band). Allerdings kommt als wesentliches Element ein Kellerspeicher hinzu. Der Keller hat eine FILO-Struktur („first in last out“), die in der praktischen Informatik einem Stack entspricht. Die Zustandsübergänge eines Kellerautomaten entsprechen denen eines ϵ-NEA.

Zusammen mit der endlichen Kontrolle von nichtdeterministischen endlichen Automaten kann ein solches Modell dazu genutzt werden, kontextfreie Sprachen zu erkennen.

Die neun vorliegenden Aufgaben beinhalten

die Konstruktion von deterministischen und nichtdeterministischen Kellerautomaten,
die Überprüfung von Sprachen auf Zugehörigkeit zur Klasse der kontextfreien Sprachen sowie
Übungen zur Selbstkontrolle des Lernenden durch Angabe von konkreten Läufen.

Lernziele sind demnach, Kellerautomaten als Erweiterung von endlichen Automaten im Zusammenhang mit kontextfreien Sprachen zu begreifen und mit Blick auf Prüfungssituationen den aufgabenbezogenen Umgang mit Kellerautomaten einzuüben und zu vertiefen.

Stefan O. Knapp

Reguläre Ausdrücke und reguläre Sprachen

Zusammenfassung

Neben endlichen Automaten und regulären Grammatiken können reguläre Sprachen durch eine weitere Systematik dargestellt werden: durch reguläre Ausdrücke. Typ-3-Sprachen, die in der Automatenschreibweise oder als Grammatik dargestellt werden, sind leicht als solche einzuordnen. Sind sie jedoch in der Mengenschreibweise angegeben, ist der Chomsky-Typ besonders aus der Perspektive von Lernenden in manchen Fällen nicht sofort zu erkennen. Dann können reguläre Ausdrücke helfen, Mengen mit wenig Aufwand als reguläre Sprachen zu identifizieren und verständlicher, anschaulicher, greifbarer machen. Insofern wird der geübte Umgang mit regulären Ausdrücken die Handhabung regulärer Sprachen und auch die Differenzierung zu kontextfreien Sprachen erleichtern.

Die 15 vorliegenden Aufgaben beinhalten

Übungen zum grundsätzlichen Verständnis für reguläre Ausdrücke als Darstellungsform für formale Sprachen,
Transformation der Darstellungen von formalen Sprachen von der Automaten- bzw. Mengenschreibweise in reguläre Ausdrücke,
Nutzung regulärer Ausdrücke zur Identifizierung regulärer Sprachen.

Zentrales Lernziel ist demnach, das Verständnis für reguläre Sprachen anhand einer weiteren Darstellungsform, dem regulären Ausdruck, zu vertiefen.

Stefan O. Knapp

Backmatter

Titel: Übungsbuch Automaten und formale Sprachen
verfasst von: Stefan O. Knapp
Verlag: Springer Fachmedien Wiesbaden
Electronic ISBN: 978-3-658-22696-1
Print ISBN: 978-3-658-22695-4
DOI: https://doi.org/10.1007/978-3-658-22696-1