Theoretische Informatik

Reguläre Sprache

Dieser Artikel behandelt die reguläre Sprache. Dabei handelt es sich um eine Typ-3-Sprache der Chomsky Hierarchie in der theoretischen Informatik.

Wann ist eine Sprache regulär? Diese Frage beantworten wir dir durch eine allgemeine Definition. Danach erfährst du, wie man einen reguläre Sprache Beweis durchführen kann und wie ein reguläre Sprache Beispiel aussieht. Zum Abschluss findest du noch alle Abschlusseigenschaften regulärer Sprachen und mögliche Entscheidungsprobleme.

Wenn du die regulären Sprachen jedoch in kurzer Zeit verstehen möchtest, schau dir einfach unser Video an. Dort findest du alles was du wissen musst, kurz und knapp zusammengefasst.

Inhaltsübersicht

Reguläre Sprachen

Eine reguläre Sprache gehört in der Informatik zum Typ 3 der formalen Sprachen und sind wichtiger Bestandteil der Textverarbeitung und Programmierung. Sie sind äquivalent zu regulären Ausdrücken, sowie deterministischen und nichtdeterministischen endlichen Automaten.

Reguläre Sprache
direkt ins Video springen
Reguläre Sprache

Wann ist eine Sprache regulär?

Eine Sprache ist regulär, wenn:

Reguläre Sprache Beweis

Um zu beweisen, dass eine Sprache regulär ist, gibt es mehrere Möglichkeiten. Zum einen kann man versuchen, die Sprache auf die Grammatik, von der sie erzeugt wurde, zurückzuführen. Außerdem kannst du probieren, die Sprache mit einem regulären Ausdruck darzustellen. Zu guter Letzt kannst du L als reguläre Sprache identifizieren, indem du einen endlichen Automaten, der die Sprache akzeptiert, konstruierst. Wie das funktioniert zeigen wir dir in unserem Reguläre Sprache Beispiel. Eine weitere Möglichkeit wäre beispielsweise auch ein Moore-Automat .

Alternativ kann man den Reguläre Sprache Beweis auch über das Pumping-Lemma herbeiführen. Wie das funktioniert, zeigen wir dir in unserem Video.

Reguläre Sprache Beispiel

Aber wie geht man nun dabei vor? Als Beispiel dient die folgende Sprache:

L=\ \left\{0^n1^{2m}\ |\ n>0,\ m\geq0\right\}
\Sigma=\ \left\{0,1\right\}

Das ist also die Sprache mit Elementen aus dem Alphabet Sigma – hier Null und Eins -, die mit beliebig vielen aber mindestens einer Null beginnen und mit keiner oder einer geraden Anzahl Einsen enden.

Die erste Bedingung sagt nun also, dass eine Sprache regulär ist, wenn sie von einer regulären Grammatik erzeugt werden kann. Für unsere Sprache L könnte eine solche Grammatik G so aussehen:

G=(N,\ T,\ P,\ S) mit
N=\left\{S,\ B,\ C\right\}
T=\ \Sigma=\left\{0,\ 1\right\}
P=\ S→0S | 0BB →1C | εC →1B
S=\left\{S\right\}

Hier benötigt man also drei Variablen oder Nichtterminale. Unser Alphabet – oft auch mit Sigma bezeichnet – besteht aus der Null und der Eins, dann das Startsymbol S und zusätzlich drei Produktionsregeln.

Dabei kann von S mit der zweiten Option also eine Null erzeugt und zur nächsten Variablen gewechselt werden oder man erzeugt mit der ersten Option beliebig viele Nullstellen. Die Variablen B und C bilden eine Schleife, mit der eine gerade Anzahl Einsen erzeugt wird. Die Wörter der Sprache können nur in B enden. Dieses Ende kann auch dann erreicht werden, wenn keine einzige 1 erzeugt wird.

Beispiel – endlicher Automat

Ein Automat, der diese Sprache akzeptiert, könnte zum Beispiel so aussehen:

Reguläre Sprache Beispiel
direkt ins Video springen
Reguläre Sprache Beispiel

Dabei wird ein Startzustand S und ein Zustandsübergang benötigt, der mit einer 0 bei S bleit. Als nächstes wird ein Zustandsübergang gebraucht, der den Automaten zwingt, mindestens eine Null zu erzeugen. Dieser Übergang lässt den Fortlauf zum neuen Zustand B zu. Damit wird eine Schleife mit dem weiteren Zustand C gebildet, wodurch eine gerade Anzahl von Einsen erzeugt werden.

Abschlusseigenschaften regulärer Sprachen

Manchmal ist es wichtig zu wissen, wie sich zwei Sprachen dieser Art verhalten, wenn man sie miteinander vermischt. Das kann zum Beispiel notwendig werden, wenn man spezielle Automaten konstruieren will. Durch solche Operationen entstehen weitere Sprachen. Wenn die neu entstandene Sprache wiederum regulär ist, gilt für diese Operation die sogenannten Abschlusseigenschaften regulärer Sprachen.

Die Abschlusseigenschaften regulärer Sprachen der Sprache L sind:

  • der Vereinigung L=L_1 \cup L_2;
  • dem Schnitt L=\ L_1 \cap L_2;
  • dem Komplement \overline{L} = \Sigma^* \setminus L;
  • der Konkatenation \left\{uv\ |\ u\ \in\ L_1\ \bigwedge\ v\in\ L_2\ \right\};
  • der Differenz L=L_1\ \setminus\ L_2;
  • und dem Kleene-Stern L^*.

Aus all diesen Operationen entstehen also jeweils neue reguläre Sprachen, wenn es sich bei den Ausgangssprachen um eine reguläre Form handelt.

Entscheidungsprobleme

Für formale Sprachen ergeben sich ein paar interessante Fragestellungen. Eine davon ist, ob ein bestimmtes Wort in der Sprache enthalten ist. Diese Frage ist für die reguläre Form entscheidbar.
Andere Fragestellungen sind zum einen das Endlichkeitsproblem, also die Frage, ob eine Sprache endlich ist, oder das Äquivalenzproblem. Hier fragt man, ob zwei Sprachen dieselben sind. Diese Frage wird gerne mit Automaten beantwortet: Man bildet erst zu beiden Sprachen Automaten, wandelt sie danach in deterministische endliche Automaten um und minimiert diese zum Schluss. Wie das funktioniert, findest du in unserem Video zu DEA minimieren . Die so entstandenen Minimalautomaten müssen für zwei äquivalente Sprachen gleich sein.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.