Reguläre Sprachen

Ein Automat definiert eine formale Sprache als Menge der von ihm akzeptierten Eingabesequenzen, die aus Eingabesymbolen zusammengesetzt sind.
Die Menge der Eingabesymbole des Automaten heißt Alphabet $\Sigma$.

$L(m)=$ formale Sprache, die von einem Modell m (hier: Automat) beschrieben wird.

Formale Sprachen haben keinerlei Ähnlichkeiten mit natürlichen Sprachen. Sie können lediglich verwendet werden, um Teile einer natürlichen Sprache zu beschreiben. Sprachen, die sowohl mithilfe von endlichen Automaten als auch mithilfe von regulären Ausdrücken beschrieben werden können, heißen Reguläre Sprachen.

Formale Darstellung der Klasse regulärer Sprachen über $\Sigma$:

• $\phi$ ist eine Reguläre Sprache
• $\forall a \in \Sigma \cup \varepsilon$
  $\to$ d.h.: (Für alle a, die Element des Alphabets $\Sigma$, das auch den leeren String enthält, sind) ist {a} eine reguläre Sprache.

• Wenn $L_{1}$ und $L_{2}$ reguläre Sprachen sind, so sind auch folgende Sprachen reguläre Sprachen:
  1. $L_{1} * L_{2} = \{ x y \vert x \in L_{1}, y \in L_{2} \}$
     (Konkatenation von $L_{1}$ und $L_{2}$)
  2. $L_{1} \cup L_{2}$
     (Vereinigung/Disjunktion von $L_{1}$ und $L_{2}$)
  3. $L*1$ (Kleene Closure von $L_{1}$)
     $\to$ Genau die Sprachen, die diese Eigenschaften aufweisen, sind Reguläre Sprachen.

     Auch folgende Ausdrücke sind Reguläre Sprachen, wenn $L_{1}$ und $L_{2}$ Reguläre Sprachen sind:

  4. $L_{1} \cap L_{2}$ (Durchschnitt von $L_{1}$ und $L_{2}$)
  5. $L_{1} - L_{2}$ (Differenz von $L_{1}$ und $L_{2}$)
  6. $\Sigma* - L_{1}$ (Komplement zu $L_{1}$)
     $\Sigma*$ ist die unendliche Menge aller nichtleeren Eingabesequenzen, die aus dem Alphabet $\Sigma$ gebildet werden können.
  7. $L_{1}^{R}$ (Umkehrung von $L_{1}$)

Alle regulären Ausdrücke können in reguläre Ausdrücke umgewandelt werden, die nur die Operationen Konkatenation, Vereinigung und Kleene Star verwenden.

Für jeden Automaten lässt sich ein regulärer Ausdruck bilden. Analog lässt sich für jeden regulären Ausdruck ein endlicher Automat konstruieren.

Zur Anschauung sollen die wichtigsten drei Operationen eines Regulären Ausdrucks mit Hilfe eines Automaten imitiert werden:

Konkatenation:

Alle Finalzustände des ersten Automaten werden mit Hilfe eines $\varepsilon$-Überganges mit dem Anfangszustand des zweiten endlichen Automaten verbunden.

Kleene closure:

Alle Finalzustände eines endlichen Automaten werden mit Hilfe von $\varepsilon$-Übergängen mit dem Anfangszustand verbunden. Dann müssen e- Übergänge vom Anfangszustand zu den Finalzuständen gezogen werden.

Vereinigung:

Es wird ein neuer Anfangszustand q'0 eingeführt, von dem neue e- Übergänge zu den alten Anfangszuständen beider Automaten führen.