Theorie Endlicher Automaten: AFN, ER, Kleene & Pumping-Lemma

Endliche Automaten und Reguläre Ausdrücke

Definition der Übergangsfunktion

Sei $q \in Q$. Die Übergangsfunktion $\delta(q)$ ist definiert als die Menge der Zustände $p$, für die eine Transition von $q$ nach $p$ existiert. $\delta(q)$ ist die Menge der Zustände, die von $q$ aus direkt durch einen Übergang erreicht werden können (z. B. gekennzeichnet durch ein Symbol).

Konvertierung: AFN mit Epsilon-Übergängen (AFN-ε)

Die Konvertierung eines AFN-ε in einen AFN ohne Epsilon-Übergänge erfolgt in folgenden Schritten:

1. Berechnen Sie den Epsilon-Abschluss ($\epsilon$-Closure) aller Zustände.
2. Definieren Sie den neuen Automaten ohne anfängliche $\epsilon$-Übergänge.
3. Setzen Sie die neuen Übergänge: Für jeden Zustand $q$ und jedes Symbol $a$ gilt: $$\delta'(q, a) = \epsilon\text{-Closure}(\delta(\epsilon\text{-Closure}(q), a))$$ Zeichnen Sie Pfeile mit dem Symbol $a$ von $q$ zu allen resultierenden Zuständen $p_1, p_2, \dots, p_n$.

Hinweis: Dieser Prozess muss für alle Zustände und mit allen Symbolen durchgeführt werden.

Regulärer Ausdruck zu Endlichem Automaten (ER → AF)

Die Konstruktion erfolgt rekursiv (z. B. Thompson-Konstruktion):

• Basisfälle: Für die leere Menge $\emptyset$, die leere Zeichenkette $\epsilon$ und das einzelne Symbol $a \in \Sigma$.
• Rekursive Fälle:
  • Wenn $L(r) = L(M_1)$ mit $M_1 = (Q_1, \Sigma, \delta_1, q_{0,1}, F_1)$ und $L(s) = L(M_2)$ mit $M_2 = (Q_2, \Sigma, \delta_2, q_{0,2}, F_2)$, dann können die Automaten für Konkatenation ($r \cdot s$), Vereinigung ($r + s$) und Kleene-Stern ($r^*$) konstruiert werden.

Endlicher Automat zu Regulärem Ausdruck (AF → ER)

Die Menge aller Sprachen, die von einem Endlichen Automaten (AF) akzeptiert werden, ist die Menge der regulären Sprachen. Dieses Set ist abgeschlossen in Bezug auf die Vereinigung, Konkatenation und den Kleene-Stern.

Kleene-Theorem

Jede reguläre Sprache wird von einem Endlichen Automaten (FA) akzeptiert, und jede Sprache, die von einem FA akzeptiert wird, ist eine reguläre Sprache.

Anwendung von Arden's Lemma

Sei $M = (Q, \Sigma, \delta, q_0, F)$ ein AF. Für jeden Zustand $q_i$ definieren wir $R_i$ als die Menge aller Wörter $w$, die $q_i$ zu einem Endzustand führen: $R_i = \{w \in \Sigma^* \mid \delta(q_i, w) \in F\}$. Beachten Sie, dass $R_0 = L(M)$.

Das Arden's Lemma besagt: Eine Gleichung der Form $X = A \cdot X \cup B$, wobei $A$ keinen $\epsilon$-Übergang enthält, hat die eindeutige Lösung $X = A^* B$. Dieses Lemma wird verwendet, um die Zustandsgleichungen in reguläre Ausdrücke umzuwandeln.

Eigenschaften Regulärer Sprachen

Wann ist eine Sprache L regulär?

1. Wenn $L$ endlich ist, ist $L$ regulär.
2. Wenn ein Regulärer Ausdruck $R$ existiert, sodass $L(R) = L$.
3. Wenn ein Endlicher Automat $M$ existiert, sodass $L(M) = L$.

HINWEIS: Um zu beweisen, dass eine Sprache regulär ist, muss man den Automaten oder den regulären Ausdruck konstruieren. Um zu beweisen, dass eine Sprache nicht regulär ist, verwendet man das Pumping-Lemma.

Das Pumping-Lemma für Reguläre Sprachen

Betrachten wir einen Deterministic Finite Automaton (DFA) $M = (Q, \Sigma, \delta, q_0, F)$. Wenn $L(M)$ unendlich ist, muss es Rückkopplungsschleifen (Zyklen) geben.

Sei $w = a_1 a_2 \dots a_{n+1} \in L(M)$ und $|w| \ge |Q| = k$. Da der Akzeptanzpfad $q_0, q_1, \dots, q_{n+1}$ mehr als $k$ Zustände enthält, muss sich mindestens ein Zustand wiederholen (Schubfachprinzip).

Pumping-Theorem (Pumping-Lemma)

Sei $L$ eine unendliche reguläre Sprache. Dann existiert eine Konstante $k$ (die Anzahl der Zustände des minimalen FA), sodass jede Zeichenkette $w \in L$ mit einer Länge $|w| \ge k$ in die Form $w = uvx$ zerlegt werden kann, wobei:

• $|v| \ge 1$ (Der mittlere Teil $v$ ist nicht leer).
• $|uv| \le k$ (Der Zyklus tritt innerhalb der ersten $k$ Zustände auf).
• Alle Ketten der Form $uv^i x \in L$ für alle $i \ge 0$.

Das Pumping-Lemma ist eine notwendige Eigenschaft aller regulären Sprachen und ermöglicht es uns, die Nicht-Regularität einer Sprache festzustellen. Es dient nicht dazu, die Regularität zu beweisen, sondern nur, um durch ein Gegenbeispiel die Nicht-Regularität zu zeigen.

Satz über die Zustandsanzahl k

Sei $M$ ein AF mit $k$ Zuständen:

1. $L(M)$ ist endlich $\iff M$ akzeptiert keine Zeichenkette der Länge $n$, wobei $k \le n < 2k$.
2. $L(M)$ ist unendlich $\iff M$ akzeptiert eine Zeichenkette der Länge $n$, wobei $k \le n < 2k$.

Praktische Überprüfung der Unendlichkeit

Um festzustellen, ob $L(M)$ unendlich ist, kann man:

1. Alle Zustände entfernen, von denen kein Weg zu einem Endzustand führt.
2. Alle Senkenzustände (Sumideros) entfernen.

Wenn danach noch Zyklen (Schleifen) im Automaten vorhanden sind, ist $L(M)$ unendlich.

Komplement einer Regulären Sprache

Um das Komplement einer regulären Sprache zu finden, konstruiert man den DFA der Originalsprache und vertauscht anschließend die Menge der Endzustände mit der Menge der Nicht-Endzustände.