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 wie beispielsweise Reguläre Ausdrücke kennen. 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, kann man anhand der Regeln und des Alphabets einer bestimmten Sprache feststellen, ob es von dieser Sprache akzeptiert wird oder eben nicht. Akzeptieren bedeutet in diesem Zusammenhang, dass sich das Wort durch die Sprache konstruieren lässt. Endliche Automaten sind abstrakte Modelle einer formalen Sprache, die Wörter, die in einer solchen formalen Sprache liegen, akzeptieren. Widerspricht der Aufbau eines Wortes den Regeln einer Sprache, wird das Wort von dem Endlichen Automaten nicht akzeptiert. Wie im Folgenden zu sehen, werden Endliche Automaten häufig durch Zustandsdiagramme dargestellt.
Links vom "=" Zeichen ist ein regulärer Ausdruck. Rechts in den geschweiften Klammern ein Teil der akzeptierten 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 Automat, der durch den oben genannten regulären Ausdruck beschrieben wurde, würde zum Beispiel das Wort 11100 oder das Wort 00111 akzeptieren, nicht aber das Wort 10 oder das Wort 0011.
In der Abbildung unten ist ein deterministischer endlicher Automat (abgekürzt DEA) zu sehen. Dessen Zustände q1 und q2 sind als Kreise (sogenannte Knoten) dargestellt. Die drei Pfeillinien (sogenannte Kanten) 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 folgende reguläre Ausdruck: ( 1 | ( 00 | 01 ) )*
Aufgabe: Weisen Sie den Zustandsübergängen des Diagramms die Symbole so zu, dass der Endliche Automat den 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:
