3. Reguläre Sprachen, NEAs, DEAs

Die Sprachen, die der endliche Automat (ein Berechnungsmodell) akzeptiert, nennt man die regulären Sprachen. Reguläre Sprachen lassen sich auch durch reguläre Ausdrücke beschreiben und durch eine reguläre Grammatik erzeugen.

Der deterministische endliche Automat (DEA)

Ein DEA ist ein minimales, d.h. ein besonders kompaktes, abstraktes, aximoatisches Modell für einen Computer. Solche Maschinen kann man sich mit einer Waschmaschine, einem automatischen Türoffner usw. Diese Maschinen haben bestimmte Zustände und je nach Zustand sich anders bei einer Eingabe verhalten.

Eine Folge s0...,sn ∈ Q von Zuständen heißt Berechnung des Automaten

Ein DEA kann das Wortproblem für bestimmte formale Sprachen lösen: er entscheidet, ob ein Wort zu einer Sprache gehört.

Ein Wort wird akzeptiert, wenn es zur Sprache gehört und verworfen, wenn es nicht dazugehört. Der DEA liest das Eingabewort zeichenweise von links nach rechts. Kein Zurückspringen möglich sowie kein Zugriff auf bereits gelesene Zeichen.

Der Speicher des DEA ist begrenzt: Er besteht nur aus einer endlichen Menge von Zuständen Die Zustandsübergänge hängen vom aktuellen Zustand und dem aktuellen Eingabezeichen ab. Die „Berechnung“ ist also eine Folge von Zustandswechseln, abhängig von der Eingabe.

Ein DEA ist ein 5-Tupel:

• Q = eine endliche, nichtleere Menge der Zustände (Zustandsmenge)

• Σ = ein (endliches) Eingabealphabet (z. B. {a, b})

• δ = eine Übergangsfunktion δ: Q × Σ → Q

• q₀ ∈ Q oder S(ein Element aus Q) = Startzustand

• F ⊆ Q = F ist eine Teilmenge von Q = Menge der akzeptierenden (End)zustände oder erreichbare Zustände

info

Das "x" in der formalen Beschreibung der Übergangsfunktion ist das kartesische Produkt. Das kartesische Produkt Q × Σ ist die Menge aller möglichen Paare (q , a), wobei:

• q ∈ Q (ein Zustand)
• a ∈ Σ (ein Eingabezeichen)

Man kombiniert jeden Zustand mit jedem Eingabezeichen → alle möglichen Kombinationen.

Die Größe des kartesischen Produktes ist gleich dem Produkt der Größen der Usprungsmengen. Wenn wir eine Menge M1 der Länge 3 haben und M2 der Länge 5 haben, beträgt das kartesische Produkt 15 (Produkt der Längen).

Die Übergangsfunktion und die erweiterte Übergangsfunktion

δ(q0, a) = q1
δ(q1, b) = q2

→ Nimmt einen Zustand und ein Zeichen und gibt den nächsten Zustand zurück

Die erweiterte Übegangsfunktion:

δ∗(q,w) beschreibt den Zustand, in dem der Automat landet, wenn er das ganze Wort w vom Zustand q aus liest.

Wozu das Ganze?

Mit δ∗ kann man formell definieren, ob ein DEA ein Wort akzeptiert:

L(M)={w ∈ Σ∗ ∣ δ∗(q0,w) ∈ F}

Iterierte Übergangsfunktion:

δ∗ (q, w) := δ|w| (q, w)

"Ein Wort w gehört zur Sprache des Automaten, wenn er nach dem Lesen in einem akzeptierenden Zustand ist."

(Sprache eines DEAs)

Sei M = (Q, Σ, δ, q0, F ) ein DEA, dann ist die von M akzeptierte Sprache definiert als

L(M) := {w ∈ Σ∗ | δ∗(q0, w) ∈ F }

Lauf eines Automaten

Die Folge der Zustände, die der Automat während der Berechnung angenommen hat, bezeichnen wir als seinen Lauf für die gewählte Eingabe. Wir sprechen auch von einem w-Lauf, wenn der Lauf sich auf die Eingabe w bezieht. Ein Lauf ist ein akzeptierender Lauf, wenn er in einem akzeptierenden Zustand endet, ansonsten nennen wir ihn verwerfenden Lauf.

Konfiguration eines Automaten

Die Konfiguration eines deterministischen endlichen Automaten (DEA) beschreibt den aktuellen Zustand des Automaten zu einem bestimmten Zeitpunkt während der Abarbeitung eines Eingabeworts. Sie besteht aus:

• Dem aktuellen Zustand q ∈ Q (wobei Q die Zustandsmenge ist).

• Dem noch zu lesenden Teil des Eingabeworts w ∈ Σ∗ (wobei Σ das Eingabealphabet ist).

Fangzustand oder Müllzustand (Trap State) in einem DEA

Ein Zustand qf der entsteht, wenn die Eingabe a bei einem Zustand qx nicht definiert ist.

Ein Fangzustand (auch Trap State, Dead State oder Fehlerzustand) ist ein Zustand in einem deterministischen endlichen Automaten (DEA), der unvermeidbar ist, sobald er erreicht wird, und aus dem der Automat nie mehr herauskommt, egal welche weiteren Eingaben kommen.

Charakterisierung regulärer Sprachen: Nichtreguläre Sprachen

Satz: Nichtregularität einer Sprache

Das Pumping Lemma wird als Werkzeug eingesetzt, um die Nichtregularität einer Sprache L zu zeigen / beweisen. Wir nehmen an, dass eine Sprache L regulär ist und beweisen mit dem Pumping Lemma, dass diese Sprache nicht regulär ist.

Wenn L erkennbar ist, dann existiert ein p ∈ ℕ, sodass für alle w ∈ L mit |w|>=p gilt: Man kann das Wort w in drei Teilen zerlegen w = xyz mit y!=ε und |xy|<=p, sodass für alle i ∈ ℕ gilt: xy^iz ∈ L.

Der nichtdeterministische endliche Automat (NEA)

Ein nichtdeterministischer endlicher Automat (NEA) lässt im Gegensatz zum DEA mehrere mögliche Übergänge für ein Eingabesymbol zu (oder gar keine). D.h. bei einem Eingabesymbol können unterschiedliche Folgezustände erreicht werden.

Er kann auch ε-Übergänge (spontane Zustandswechsel ohne Eingabe) haben. ε-Übergänge sind z.B. nützlich um zwei Automaten zu verknüpfen, ohne dass dazu Zeichen eingelesen werden müssen.

Für die Einbeziehung der ε-Übergänge müssen wir definieren, welche Zustände wir von p (p = Platzhalter für bestimmten Zustand) aus erreichen können, ohne ein Zeichen zu lesen. Diese Zustände werden von der Zustandsmenge E(p) dargestellt.

Es gilt also:

E(p) := {q | q ist von p durch eine Sequenz von ≥ 0 ε-Übergängen erreichbar}

Es ist also eine Menge von Zuständen – nämlich genau die, die man von Zustand p aus erreichen kann, indem man nur ε-Übergänge benutzt.

Die Übergangsfunktion weist jedoch jedem Paar aus Zustand und Eingabezeichen nicht einen einzelnen Folgezustand zu, sondern eine (eventuell leere) Menge von Folgezuständen.

Formale Definition eines NEA

Ein NEA ist ein 5-Tupel A=(Q,Σ,δ,q0,F), wobei:

• Q eine endliche Menge von Zuständen,

• Σ das Eingabealphabet,

• δ ⁣: δ:Q × (Σ ∪ {ε} ) → P(Q) die Übergangsfunktion (gibt eine Menge möglicher Folgezustände zurück, inkl. ε-Übergänge),

• q0 ∈ Q der Startzustand,

• F ⊆ Q die Menge der akzeptierenden Zustände.

P(Q) bezeichnet die Menge aller Teilmengen von Q (= {Z | Z ⊆ Q} )

Wir wollen ausdrücken können, welche Zustände wir von p aus erreichen können, ohne ein Zeichen zu lesen. Diese Zustandsmenge notieren wir mit E(p)

Iterierte Übergangsfunktion eines NEAs

δ∗(P , w) := δ|w|(P , w)

*Die erweiterte Übergangsfunktion δ∗ für eine Zustandsmenge P und ein Wort w ist definiert als die ∣w∣-fache Anwendung der Übergangsfunktion δ auf P und w*

δ∗ simuliert die Abarbeitung des Worts w auf dem Automaten:

• Starte mit der Zustandsmenge P,

• Verarbeite Schritt für Schritt jedes Symbol von w,

• Gib die finale Zustandsmenge zurück.

Sprache eines DEAs

Sei M = (Q,Σ,δ,q0,F) ein DEA, dann ist die von M akzeptierte Sprache definiert als L(M) := {w ∈ Σ∗ | δ∗(q0, w) ∈ F }

Die Sprachen, die von einem DEA akzeptiert werden, haben viele nützliche Eigenschaften und bilden eine interessante Struktur. Aus diesem Grunde geben wir dieser Sprachfamilie einen Namen, nämlich reguläre Sprachen.

Wenn L eine Sprache ist, für die es einen DEA gibt, der L akzeptiert, nennen wir L eine reguläre Sprache.

Umwandlung von ε-NEA zu NEA

Durch die Umwandlung eines ε-NEA in ein NEA zeigen, wir dass die Automaten äquivalent sind. Ein-Symbol-Pfade sind all diejenigen Pfade, die genau eine Kante mit einem Symbol aus dem Eingabealphabet und sonst nur εs als Kantenbeschriftung enthalten

Ziel: Entferne alle ε-Übergänge, behalte die akzeptierte Sprache.

Vorgehen:

1. Finde alle Ein-Symbol-Pfade:

   • Pfade mit genau einem Symbol aus dem Eingabealphabet Σ
   • Rest sind nur ε-Kanten
   • Beispiel: q0 --ε--> q1 --a--> q2 --ε--> q3 → wird q0 --a--> q3

2. Ersetze jeden solchen Pfad durch eine direkte Kante

3. Streiche alle ε-Kanten

4. Falls vom Startzustand ein ε-Pfad zu einem Endzustand führt, dann:

   • mache auch den Startzustand zum Endzustand

Ergebnis: Ein NEA ohne ε-Übergänge, aber mit gleicher Sprache.

Umwandlung von NEA zu DEA

Das Ziel ist es, einen deterministischen Automaten (DEA) zu bestimmen, der die gleiche Sprache wie ein gegebener NEA akzeptiert. Hintergrund ist, dass wir damit zeigen, dass ein NEA nicht mächtiger ist, als ein DEA. Aus jedem NEA lässt sich nämlich ein DEA konstruieren.

Die Grundidee ist, dass die Zustände des DEAs eine Teilmenge von Zuständen des NEAs sind (Potenzmenge 2^Q). Ein Zustand im DEA repräsentiert eine Menge von möglichen Zuständen im NEA.

info

Eine Potenzmenge ist die Menge aller Teilmengen einer gegebenen Menge.

Konstruktion:

• Q' = 2^Q (alle Teilmengen der Zustände Q von NEA)

• Startzustand q0' = {q0} (Menge mit dem Startzustand des NEA)

• Endzustände F' = {T ⊆ Q | T ∩ F ≠ ∅} (T ist eine Teilmenge von Q | T enthält mindestens einen Endzustand aus F)

• Übergangsfunktion: δ′(T, a) = {q| es gibt ein qt ∈ T , sodass δ(qt , a) = q ist} (also: von jedem Zustand q ∈ T aus schauen, wohin a führt, und alle Ziele vereinigen)

Der Satz von Kleene

Die Menge der regulären Sprachen und die Menge der Sprachen, die durch einen regulären Ausdruck beschrieben werden können, sind identisch.

Grundsätzlich definiert der Satz von Kleene, was reguläre Sprachen sind und mit welchen Regeln sie entstehen können.

Alle regulären Sprachen über einem Alphabet Σ gehören zur kleinsten Sprachenfamilie, die:

• Die leere Sprache ∅ enthält
• Für jedes Zeichen a ∈ Σ die Sprache {a} enthält
• Abgeschlossen ist unter folgenden Operationen:
• Vereinigung ( ∪ )
• Konkatenation ( · )
• Kleene-Stern ( * )

Das bedeutet, dass reguläre Sprachen aus einfachen Basis-Sprachen entstehen und man darf sie mit bestimmten Operationen kombinieren. Die "kleinste" Familie bedeutet: Es sind genau nur die Sprachen, die man durch diese Schritte konstruieren kann – nicht mehr.

🔁 Beispiel:

Angenommen, unser Alphabet ist Σ={a,b}

Basis-Sprachen, die daraus entstehen sind:

• ∅
• {a}
• {b}

Daraus bauen wir, mit den oben bestimmten Operationen, reguläre Sprachen:

• {a}∪{b}={a,b}

• {a}⋅{b}={ab}

• {a}∗={ε,a,aa,aaa,…}

info

Diese konstruktive Definition entspricht den Regeln zum Bauen von regulären Ausdrücken. Reguläre Ausdrücke sind also nur ein anderer "Schreibstil" für diese Sprachenfamilie.

Minimierung von DEAs

Wenn wir einen NEA in einen DEA umwandeln, entstehen exponentiell mehr Zustände als im NEA. Hat der NEA k Zustände, werden durch die Umwandlung 2^k Zustände entstehen.

Einen zentralen Punkt bei der Minimierung von DEAs bildet der Begriff des äquivalenten Zustandspaares.

Äquivalenz von zwei Zuständen

Sei M = (Q, Σ, δ, q0, F ) ein DEA. Wir nennen zwei Zustände p, q ∈ Q äquivalent, falls für alle w ∈ Σ∗ gilt, dass δ∗(p, w) ∈ F ⇐⇒ δ∗(q, w) ∈ F.

Moore und Mealy-Automaten

Moore und Mealy-Maschinen sind Automaten, die eine Ausgabe produzieren. Wir erweitern unsere formale Definition eines DEA/NEA um eine Ausgabefunktion γ. Diese Automaten nennen wir auch sequentielle Maschinen.

Der Unterschied zwischen beiden Modellen liegt in der Ausgabe funktion γ:

• Bei Moore-Automat hängt die Funktion nur vom aktuellen Zustand q ab
• Bei Mealy-Automaten hängt die Funktion vom aktuellen Zustand q und vom aktuellen Eingabesymbole aus Σ ab

Wir können deshalb die Funktion eines Moore-Automaten als γ: Q -> Γ formal definieren. Für das Mealy-Automat hingegen: γ: Q x Σ -> Γ.

Beide Modelle sind in ihrer Berechnungsfähigkeit äquivalent.

Moore-Maschine (formale Definition)

Eine Moore-Maschine A hat die Form A=(Q, 6, Σ, δ, λ, q0), mit:

• Q : ist eine nichtleere, endliche Menge und heißt Zustandsmenge,
• Σ : ist das Eingabealphabet,
• Γ : ist das Ausgabealphabet,
• δ : mit δ : Q × Σ −→ Q ist die Transitionsfunktion,
• λ : mit λ : Q −→ Γ ist die Ausgabefunktion und
• q0 : mit q0 ∈ Q ist der Anfangszustand

Mealy-Maschine (formale Definition)

Eine Mealy-Maschine A hat die Form A=(Q, 6, Σ, δ, λ, q0), mit:

• Q : ist eine nichtleere, endliche Menge und heißt Zustandsmenge,
• Σ : ist das Eingabealphabet,
• Γ : ist das Ausgabealphabet,
• δ : mit δ : Q × Σ −→ Q ist die Transitionsfunktion,
• λ : mit λ : Q x Σ −→ Γ ist die Ausgabefunktion und
• q0 : mit q0 ∈ Q ist der Anfangszustand

Im Gegensatz zu endlichen Akzeptoren haben diese Maschinen keine Endzustände, sie reagieren auf Eingabefolgen, also Wörter über dem Eingabealphabet, durch Ausgabefolgen.

Zustandsdiagramme und Automatentafeln von endlichen Automaten

Im Gegensatz zu endlichen Akzeptoren (NEA, DEA) haben Moore- und Mealy-Maschinen keine Endzustände. Sie reagieren auf Eingabefolgen und produzieren eine Ausgabe. Eine Maschine A beschreibt also eine Funktion fA : Σ∗ −→ Γ∗. Weil bei Eingabe eines Eingabesymbols aus Σ auch nur ein Ausgabesymbol aus Γ produziert wird, sind die Ausgabefolgen genauso lang wie die Eingabefolgen.

20 Fragen und Übungen zu Regulären Sprachen & Automaten

Grundlagen und Definitionen (DEA/NEA)

• Nenne die fünf Komponenten (5-Tupel) der formalen Definition eines DEA und gib an, welche Komponente die Speicherbegrenzung des Automaten widerspiegelt.

• Erkläre den wesentlichen Unterschied zwischen der Transitionsfunktion (δ) eines DEA und der Übergangsfunktion (δ) eines NEA. (Tipp: Achte auf die Zielmenge der Funktion.)

• Was entscheidet ein DEA beim Wortproblem und welche Eigenschaft der Sprache L wird durch die erweiterte Übergangsfunktion δ∗ formell beschrieben, um diese Entscheidung zu treffen?

• Beschreibe den begrenzten Speicher eines DEA und definiere, was der Lauf eines Automaten während der Berechnung eines Wortes w ist.

• Wofür sind ϵ-Übergänge bei einem NEA nützlich und was ist die ϵ-Abschlussmenge E(p) eines Zustands p (formell definiert)?

Formale Notation und Mathematik

• Kartesisches Produkt (Übung): Sei die Zustandsmenge Q={q0​,q1​,q2​} und das Eingabealphabet Σ={a,b}. Gib das kartesische Produkt Q×Σ vollständig an.

• Potenzmenge (Übung): Sei Q={q1​,q2​}. Bestimme die Potenzmenge P(Q) (die Zustandsmenge des äquivalenten DEA) und nenne deren Mächtigkeit (Größe).

• Konfiguration (Definition): Erkläre, woraus die Konfiguration eines Automaten zu einem bestimmten Zeitpunkt besteht.

• Akzeptierte Sprache (Notation): Schreibe die formale Definition der von einem Automaten M akzeptierten Sprache L(M) auf und erkläre in eigenen Worten, was die Bedingung δ∗(q0​,w)∈F bedeutet.

Zustandsmaschinen und Umwandlung

• Trap State (Konzept): Erkläre die Funktion eines Fangzustands (Trap State) in einem DEA und warum er als „unvermeidbar“ gilt, sobald er erreicht wird.

• NEA zu DEA (Prinzip): Erkläre die Grundidee der Umwandlung eines NEA in einen äquivalenten DEA (Potenzmengenkonstruktion), insbesondere wie die Zustände des neuen DEA gebildet werden.

• NEA zu DEA (Endzustände): Wie wird die Menge der Endzustände F′ des neuen DEA aus der Zustandsmenge Q und den Endzuständen F des ursprünglichen NEA definiert? (Gib die formale Mengennotation an: F′=…)

• ϵ-NEA zu NEA (Umwandlung): Beschreibe die vier Schritte zur Umwandlung eines ϵ-NEA in einen NEA (Entfernung der ϵ-Übergänge), inklusive der Regel zur Handhabung des Startzustands.

Moore- und Mealy-Automaten

• Ausgabefunktion (Unterschied): Gib die formalen Definitionen der Ausgabefunktion λ für Moore-Maschinen und Mealy-Maschinen an und fasse den Unterschied zusammen.

• Endzustände (Konzept): Haben Moore- und Mealy-Maschinen Endzustände? Begründe deine Antwort anhand ihrer Funktion im Vergleich zu DEA/NEA.

Mealy-Automatentafel (Übung): Wie wird ein Übergang δ(q1​,a)=q2​ mit der Ausgabe λ(q1​,a)=c in einer Mealy-Automatentafel dargestellt?

Satz von Kleene und Minimierung

• Satz von Kleene (Konzept): Was besagt der Satz von Kleene bezüglich der regulären Sprachen und Sprachen, die durch reguläre Ausdrücke beschrieben werden?

• Satz von Kleene (Operationen): Welche drei Operationen muss eine Sprachenfamilie (zusammen mit der leeren Sprache ∅ und den Basissprachen {a}) mindestens enthalten, um die Menge aller regulären Sprachen zu erzeugen?

• Äquivalenz von Zuständen (Definition): Definiere, wann zwei Zustände p und q eines DEA äquivalent sind.

• Minimierung (Ziel): Was ist der Hauptgrund für die Minimierung von DEAs in der Theoretischen Informatik und welche Konsequenz der NEA-zu-DEA-Umwandlung macht die Minimierung besonders relevant?