Reguläre Sprachen und endliche Automaten

Reguläre Sprachen

Betrachten Sie das Alphabet Σ = {a, b}. Für jede natürliche Zahl n gibt es nur eine endliche Anzahl an Wörtern der Länge n. Diese Strings lassen sich lexikographisch ordnen: 0 für die Länge 0, Wörter der Länge 1, und allgemein für die Länge n+1. Beispiel: ε → 0, a → 1, b → 2, aa → 3, ab → 4 ...

Allgemein gilt: Da alle endlichen Alphabete abzählbar sind, können wir die Zeichen in einer beliebigen Reihenfolge anordnen: Σ = {a₀, a₁, a₂, ..., aₙ}. Die Menge aller Sprachen über Σ ist jedoch nicht abzählbar unendlich.

Reguläre Sprachen und reguläre Ausdrücke

Eine Sprache über einem Alphabet Σ ist regulär, wenn sie rekursiv wie folgt definiert ist:

• a) ∅ ist eine reguläre Sprache (leere Sprache).
• b) {ε} ist eine reguläre Sprache (Sprache mit der leeren Zeichenkette).
• c) Für alle a ∈ Σ ist {a} eine reguläre Sprache.
• d) Wenn A und B reguläre Sprachen sind, dann sind auch A ∪ B, A · B und A* reguläre Sprachen.
• e) Jede andere Sprache ist nur dann regulär, wenn sie durch eine endliche Anzahl von Operationen gemäß d) gebildet werden kann.

Beispiele

Σ = {a, b}: {ε}, {a}, {b}, {a, b} = {a} ∪ {b}, {ab} = {a} · {b}, {a}*.

Hinweis: Nicht jede Sprache ist regulär. L₂ = {aⁱbⁱ | i ≥ 0} ist beispielsweise nicht regulär.

Reguläre Ausdrücke

Reguläre Ausdrücke bezeichnen reguläre Sprachen. Ein Ausdruck r bezeichnet die Sprache L(r).

Deterministische endliche Automaten (DFA)

Ein DFA M = (Q, Σ, δ, q₀, F) besteht aus:

1. Einem Eingabealphabet Σ.
2. Einer endlichen Menge Q von Zuständen.
3. Einem Startzustand q₀ ∈ Q.
4. Einer Menge F ⊆ Q von Endzuständen.
5. Einer Übergangsfunktion δ: Q × Σ → Q.

Ein DFA kann als Zustandsdiagramm (gerichteter Graph) oder als Übergangstabelle dargestellt werden.

AFD und Sprachen

Die von einem DFA M akzeptierte Sprache L(M) ist die Menge aller Wörter w ∈ Σ*, die M von q₀ in einen Zustand f ∈ F überführen.

Nichtdeterministische endliche Automaten (NFA)

Ein NFA erlaubt bei gleicher Eingabe den Übergang in mehrere oder gar keinen Zustand. Die Übergangsrelation ist δ: (Q × Σ) → 2^Q.

Gleichwertigkeit von NFA und DFA

Jeder NFA kann in einen äquivalenten DFA umgewandelt werden (Potenzmengenkonstruktion). Ein NFA mit n Zuständen kann im schlimmsten Fall einen DFA mit 2ⁿ Zuständen erfordern.

AF mit Epsilon-Übergängen (ε-NFA)

Ein ε-NFA erlaubt Übergänge zwischen Zuständen, ohne ein Eingabesymbol zu verbrauchen. Die Epsilon-Hülle ε(q) definiert alle Zustände, die von q aus ohne Eingabe erreichbar sind.