Diese Seiten können nicht richtig dargestellt werden, da Sie Ihren Internet Explorer mit aktivierter Kompatibiltätsansicht verwenden. Wir empfehlen 'fu-berlin.de' aus der Liste der Websites mit aktivierter Kompatibilitätsansicht zu entfernen:
- Blenden Sie bitte in Ihrem Internet Explorer die Menüleiste ein, indem Sie entweder 'Alt' drücken oder in der Adressleiste mit der rechten Maustaste klicken und dann 'Menüleiste' auswählen.
- Klicken Sie auf 'Extras' und wählen das Menü 'Einstellungen der Kompatibilitätsansicht' aus.
- Wählen Sie unter 'Zur Kompatibilitätsansicht hinzugefügte Websites' 'fu-berlin.de' aus.
- Klicken Sie auf 'Entfernen'.
Theoretische Informatik (2. Semester)
Im Modul Grundlagen der Theoretischen Informatik lernen die Studierenden verschiedene Typen von formalen Sprachen kennen.
Die zwei folgenden Aufgaben beschäftigen sich mit Regulären Ausdrücken und Endlichen Automaten.
1. Reguläre Ausdrücke
Bei einem Regulären Ausdruck handelt es sich um eine Sprache, die bestimmten Regeln unterliegt und aus einem definierten Alphabet besteht. Betrachtet man ein bestimmtes Wort (Symbolketten), kann man anhand der Regeln und des Alphabets einer bestimmten Sprache feststellen, ob es in dieser Sprache liegt oder nicht. In einer Sprache liegen bedeutet in diesem Zusammenhang, dass sich das Wort durch die Sprache konstruieren lässt.
Links vom "=" Zeichen ist ein regulärer Ausdruck. Rechts in den geschweiften Klammern ein Teil der konstruierbaren Wörter.
( 00 | 111 )* = { 00, 111, 00111, 11100, 0011100, ... }
Das Alphabet besteht aus den Symbolen 0 und 1. Unmittelbar nebeneinander geschriebene Symbole (wie 00 und 111) werden nacheinander erkannt (es liegt eine Und-Verknüpfung vor). Bei Symbolen, die mit einem senkrechten Strich ( | ) getrennt sind, wird nur die eine oder die andere Seite erkannt (Oder-Vernüpfung). Ein Stern ( * ) zeigt an, dass die markierten Symbole oder die Symbole in den Klammern beliebig oft vorkommen können.
Der reguläre Ausdruck kann zum Beispiel das Wort 11100 oder das Wort 00111 konstruieren, nicht aber das Wort 10 oder das Wort 0011.
Gegeben ist der folgende Reguläre Ausdruck: ( 1 | ( 00 | 01 ) )*
Welches der folgenden Wörter lässt sich durch den regulären Ausdruck konstruieren?
Alle Wörter, die durch den gegebenen regulären Ausdruck konstruiert werden können, müssen mit 1, 00 oder 01 beginnen. Darauffolgend können sich diese Symbolketten beliebig oft wiederholen. Auf diese Weise kann das Wort 011 konstruiert werden, nicht aber die anderen gegeben Wörter.
Klicken Sie auf Weiter, um zur nächsten Teilaufgabe zu gelangen.
2. Endliche Automaten
Endliche Automaten sind abstrakte Modelle einer formalen Sprache. Sie können Wörter akzeptieren oder nicht akzeptieren. Falls der Aufbau eines Wortes den Regeln der Sprache widerspricht, wird das Wort nicht akzeptiert. In der Abbildung unten ist ein deterministischer endlicher Automat zu sehen, dessen Zustände q1 und q2 als Kreise dargestellt sind. Die drei Pfeillinien zwischen den Zuständen stehen für Zustandsübergänge. Der Zustand q1 ist sowohl der Startzustand (zu erkennen an dem hineinführenden Pfeil von links) als auch der akzeptierende Zustand (zu erkennen an dem Doppelkreis), was bedeutet, dass der Automat in diesem Zustand startet und hier auch das letzte Symbol vom Wort gelesen haben muss, damit er es akzeptiert. Zustand q2 ist nicht akzeptierend. Wenn man von Zustand q1 ausgeht und den Pfeillinien folgt, lassen sich die Regeln der Sprache nachvollziehen.
Gegeben ist der Reguläre Ausdruck ( 1 | ( 00 | 01 ) )*
Aufgabe: Weisen Sie den Zustandsübergängen des Diagramms die Symbole so zu, dass der Endliche Automat diesen Regulären Ausdruck darstellt.
Hinweis: Ziehen Sie die Antworten per Drag & Drop in die Kreise.
Sie erhalten ein Feedback zu den einzelnen Antworten, indem Sie auf das klicken.
Die richtige Lösung ist nachfolgend zu sehen:
