Mit Google fortfahren
Reguläre Sprache: Automaten, Ausdrücke und Beweise
Eine reguläre Sprache ist eine Menge von Wörtern, die ein endlicher Automat erkennen kann. Dieselbe Sprache lässt sich auch durch einen regulären Ausdruck oder eine reguläre Grammatik beschreiben.
Auf dieser Seite lernst du, zwischen diesen Darstellungen zu wechseln, einen Automaten systematisch zu testen und reguläre von nichtregulären Sprachen zu unterscheiden.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Was macht eine Sprache regulär?
Ein Alphabet $\Sigma$ ist eine endliche Menge von Zeichen. Für $\Sigma=\{0,1\}$ sind zum Beispiel 0, 101 und das leere Wort Wörter über diesem Alphabet. Die Menge aller endlichen Wörter heißt $\Sigma^*$. Das leere Wort wird mit $\varepsilon$ bezeichnet.
Eine formale Sprache ist eine Teilmenge von $\Sigma^*$: Sie wählt also bestimmte Wörter nach einer festgelegten Bedingung aus.
Reguläre Sprache
Eine Sprache $L\subseteq\Sigma^*$ heißt regulär, wenn ein endlicher Automat existiert, der genau die Wörter aus $L$ akzeptiert. Gleichwertig kann $L$ durch einen regulären Ausdruck oder eine reguläre Grammatik beschrieben werden.
„Endlich“ bezieht sich dabei auf die Zahl der Zustände des Automaten, nicht auf die Zahl der Wörter. Eine reguläre Sprache darf unendlich viele Wörter enthalten.
Beispielsweise ist die Sprache aller Binärwörter, die auf 01 enden, unendlich. Ein Automat braucht trotzdem nur zu speichern, welche Endung bisher relevant ist.
Regulär ist eine Sprache, sobald eine passende reguläre Darstellung existiert. Eine ungeeignete oder nichtreguläre Grammatik beweist daher nicht, dass die Sprache selbst nicht regulär ist.
Drei gleichwertige Beschreibungen
Reguläre Sprachen lassen sich auf drei grundlegende Arten darstellen:
- Ein deterministischer endlicher Automat (DEA) verarbeitet ein Wort Zeichen für Zeichen. Für jeden Zustand und jedes Zeichen gibt es genau einen Folgezustand.
- Ein regulärer Ausdruck beschreibt erlaubte Zeichenfolgen mit Operationen wie Alternative, Verkettung und Wiederholung.
- Eine reguläre Grammatik erzeugt Wörter mit stark eingeschränkten Regeln. Bei einer rechtslinearen Grammatik kann eine Regel etwa die Form $A\to aB$ haben.
Die Darstellungen sehen verschieden aus, bestimmen aber dieselbe Sprachklasse. Deshalb kannst du die Form wählen, die für eine Aufgabe am günstigsten ist.
Betrachte alle Binärwörter, die auf 01 enden.
Der reguläre Ausdruck lautet:
$$(0+1)^*01$$
Dabei bedeutet + eine Alternative: An jeder Stelle darf 0 oder 1 stehen. Der Stern erlaubt beliebig viele Wiederholungen, auch keine. Das abschließende 01 erzwingt die gewünschte Endung.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Ein DEA besitzt nur viele Zustände. Der Ausdruck $(0+1)^*$ erlaubt Zeichen aus $\{0,1\}$. Eine Sprache ist schon dann regulär, wenn passende reguläre Darstellung existiert.
Einen Erkenner vollständig konstruieren
Wir konstruieren einen DEA für die Sprache
$$L=\{w\in\{0,1\}^*\mid w\text{ endet auf }01\}.$$
Der Automat muss nicht das ganze Wort speichern. Er braucht nur drei Situationen zu unterscheiden:
- $q_0$: Die bisherige Endung hilft noch nicht oder endet auf
1. - $q_1$: Das bisher gelesene Wort endet auf
0. - $q_2$: Das bisher gelesene Wort endet auf
01.
$q_0$ ist der Startzustand. Nur $q_2$ ist akzeptierend.
| aktueller Zustand | Eingabe 0 | Eingabe 1 |
|---|---|---|
| $q_0$ | $q_1$ | $q_0$ |
| $q_1$ | $q_1$ | $q_2$ |
| $q_2$ | $q_1$ | $q_0$ |
Warum führen die Übergänge von $q_2$ wieder weg? Nach einer weiteren 0 endet das neue Wort nur noch auf 0. Nach einer weiteren 1 endet es auf 11. In beiden Fällen lautet die aktuelle Endung nicht mehr 01.
Teste das Wort 1101:
- Start in $q_0$.
1: $q_0\to q_0$.1: $q_0\to q_0$.0: $q_0\to q_1$.1: $q_1\to q_2$.
Das Wort endet in $q_2$ und wird akzeptiert. Das passt zur Sprachbedingung: 1101 endet auf 01.
Beim Wort 1011 lautet der letzte Übergang dagegen $q_2\to q_0$. Es wird abgelehnt, weil es nicht auf 01 endet.
Eine gleichwertige rechtslineare Grammatik ist:
- $S\to 0A\mid 1S$
- $A\to 0A\mid 1B$
- $B\to 0A\mid 1S\mid\varepsilon$
Die Nichtterminale $S$, $A$ und $B$ entsprechen den Zuständen $q_0$, $q_1$ und $q_2$. Die Regel $B\to\varepsilon$ beendet eine Ableitung genau im akzeptierenden Zustand.
So lässt sich der DEA als Erkenner umsetzen:
- Setze den aktuellen Zustand auf $q_0$.
- Lies das Wort von links nach rechts.
- Ersetze den Zustand nach jedem Zeichen mithilfe der Übergangstabelle.
- Akzeptiere nach dem letzten Zeichen genau dann, wenn der Zustand $q_2$ ist.
Reguläre Sprachen sicher kombinieren und prüfen
Reguläre Sprachen sind unter mehreren Operationen abgeschlossen. Das bedeutet: Wendest du eine dieser Operationen auf reguläre Sprachen an, ist auch das Ergebnis regulär.
Wichtige Abschlussoperationen sind:
- Vereinigung $L_1\cup L_2$,
- Schnitt $L_1\cap L_2$,
- Komplement $\Sigma^*\setminus L$,
- Differenz $L_1\setminus L_2$,
- Konkatenation $L_1L_2$,
- Kleene-Stern $L^*$,
- Spiegelung der Wörter.
Bei der Konkatenation werden je ein Wort aus $L_1$ und ein Wort aus $L_2$ aneinandergefügt. Beim Kleene-Stern dürfen beliebig viele Wörter aus $L$ aufeinanderfolgen; auch null Wörter sind erlaubt. Deshalb gehört $\varepsilon$ immer zu $L^*$.
Für das Komplement vertauschst du in einem vollständigen DEA akzeptierende und nicht akzeptierende Zustände. Die Vollständigkeit ist wichtig: Zu jedem Zustand und jedem Zeichen muss ein Übergang vorhanden sein.
Auch viele Fragen über reguläre Sprachen sind entscheidbar. Es gibt also ein Verfahren, das nach endlich vielen Schritten eine korrekte Ja-Nein-Antwort liefert. Dazu gehören:
- Wortproblem: Gehört ein Wort zu $L$?
- Leerheitsproblem: Gilt $L=\emptyset$?
- Endlichkeitsproblem: Enthält $L$ nur endlich viele Wörter?
- Äquivalenzproblem: Gilt $L_1=L_2$?
- Inklusionsproblem: Gilt $L_1\subseteq L_2$?
Beim Wortproblem simulierst du den Automaten. Für die Leerheit prüfst du, ob vom Startzustand überhaupt ein akzeptierender Zustand erreichbar ist. Für die Äquivalenz kannst du beide Beschreibungen in DEAs umwandeln und ihre Startzustände auf gleiches Akzeptanzverhalten prüfen.
Wo endliche Automaten an ihre Grenze kommen
Ein endlicher Automat kann nur endlich viele Situationen unterscheiden. Er kann beispielsweise speichern, ob die Anzahl gelesener Einsen gerade oder ungerade ist. Er kann aber keine beliebig große Zahl exakt speichern, um sie später mit einer zweiten Zahl zu vergleichen.
Die Sprache
$$L=\{0^m1^m\mid m\ge 0\}$$
enthält Wörter mit gleich vielen Nullen und Einsen, wobei alle Nullen vor allen Einsen stehen. Beispiele sind $\varepsilon$, 01, 0011 und 000111.
Diese Sprache ist nicht regulär. Ein Beweis verwendet das Pumping-Lemma.
Pumping-Lemma
Ist $L$ regulär, dann gibt es eine Zahl $n$, sodass jedes ausreichend lange Wort $w\in L$ als $w=xyz$ zerlegt werden kann. Dabei gilt $y\ne\varepsilon$, $|xy|\le n$ und $xy^kz\in L$ für jedes $k\ge 0$.
Für einen Widerspruch nehmen wir an, $L$ sei regulär, und wählen das Wort $w=0^n1^n$. Wegen $|xy|\le n$ liegt das nichtleere Stück $y$ vollständig im ersten Nullblock. Es besteht also nur aus Nullen.
Setzen wir $k=0$, wird $y$ entfernt. Das neue Wort besitzt weniger als $n$ Nullen, aber weiterhin $n$ Einsen. Es gehört nicht zu $L$. Das widerspricht dem Pumping-Lemma. Daher ist $L$ nicht regulär.
Das Pumping-Lemma liefert eine notwendige Eigenschaft regulärer Sprachen. Ein Widerspruch kann Nichtregularität beweisen. Eine gelungene Zerlegung eines einzelnen Wortes beweist dagegen noch keine Regularität.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Reguläre Sprache
- wird von einem endlichen Automaten erkannt
- wird durch einen regulären Ausdruck beschrieben
- wird durch eine reguläre Grammatik erzeugt
- bleibt unter wichtigen Operationen regulär
- besitzt entscheidbare Prüfprobleme
- hat nur endlich viele unterscheidbare Automatensituationen
- lässt sich von nichtregulären Sprachen abgrenzen