Reguläre Sprache
Dieser Artikel und das Video behandeln 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.
Wann ist eine Sprache regulär?
Eine Sprache ist regulär, wenn:
- die Sprache von einer regulären Grammatik erzeugt wird;
- endliche Automaten sie akzeptieren;
- und die Sprache durch einen regulären Ausdruck dargestellt werden kann.
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:
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:
mit
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:
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 
sind:
- der Vereinigung
; - dem Schnitt
; - dem Komplement
; - der Konkatenation
; - der Differenz
; - und dem Kleene-Stern
.
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.