Zum Inhalt springen

Nichtdeterministischer endlicher Automat

Aus FLBK-Wiki
Version vom 8. November 2026, 09:11 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Ein nichtdeterministischer endlicher Automat (NEA) darf bei einem Zeichen mehrere Wege offenhalten. Das macht viele Modelle kürzer und übersichtlicher. ==Definition== Ein NEA ist ein 5-Tupel <math>A = (Q, \Sigma, \delta, q0, F)</math> wie beim DEA, aber mit der Übergangsfunktion <math>\delta: Q \times \Sigma \to P(Q)</math>. <math>P(Q)</math> ist die Potenzmenge von <math>Q</math>, die Menge aller Menge#Teilme…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Ein nichtdeterministischer endlicher Automat (NEA) darf bei einem Zeichen mehrere Wege offenhalten. Das macht viele Modelle kürzer und übersichtlicher.

Definition

Ein NEA ist ein 5-Tupel [math]\displaystyle{ A = (Q, \Sigma, \delta, q0, F) }[/math] wie beim DEA, aber mit der Übergangsfunktion [math]\displaystyle{ \delta: Q \times \Sigma \to P(Q) }[/math]. [math]\displaystyle{ P(Q) }[/math] ist die Potenzmenge von [math]\displaystyle{ Q }[/math], die Menge aller Teilmengen von [math]\displaystyle{ Q }[/math]. Zur Potenzmenge gehören auch die leere Menge [math]\displaystyle{ \emptyset }[/math] und [math]\displaystyle{ Q }[/math] selbst.

Zu einem Zustand und einem Zeichen gibt es deshalb keinen, einen oder mehrere Folgezustände. Der Wert [math]\displaystyle{ \delta(q, a) = \emptyset }[/math] bedeutet: kein Folgezustand.

Manche Aufgaben nennen statt der Funktion eine Übergangsrelation. Beide beschreiben dasselbe: Die Relation enthält das Tripel [math]\displaystyle{ (p, a, q) }[/math] genau dann, wenn [math]\displaystyle{ q \in \delta(p, a) }[/math] gilt.

Übergangsgraph und Übergangstabelle entsprechen den Darstellungsformen des DEA. Im Graphen können einen Zustand für dasselbe Zeichen kein, ein oder mehrere Pfeile verlassen. In der Tabelle steht in jeder Zelle eine Menge von Folgezuständen, ein Strich – steht für „kein Folgezustand“. Der Pfeil → markiert den Startzustand, der Stern * die Endzustände.

Wortakzeptanz

Ein NEA akzeptiert ein Wort, wenn mindestens ein Pfad das ganze Wort liest und in einem Endzustand endet. Pfade, die abbrechen oder nicht in einem Endzustand enden, sprechen nicht dagegen. Abgelehnt wird ein Wort erst, wenn kein Pfad das leistet.

Ein Pfad bricht ab, wenn der aktuelle Zustand für das nächste Zeichen keinen Folgezustand hat. Anschaulich verfolgt der NEA alle Pfade gleichzeitig. Die akzeptierte Sprache [math]\displaystyle{ L(A) }[/math] besteht aus allen Wörtern, die der NEA akzeptiert.

Unterschied zum DEA

Merkmal DEA NEA
Folgezustände genau einer je Zustand und Zeichen keiner, einer oder mehrere
Fehlende Übergänge nicht erlaubt, ein vollständiger DEA ergänzt sie durch einen Fehlerzustand erlaubt, der Pfad bricht dort ab
Akzeptanz der eine Lauf endet in einem Endzustand mindestens ein Pfad endet in einem Endzustand
Prüfaufwand ein Lauf je Wort mehrere Pfade je Wort, im ungünstigen Fall müssen alle verfolgt werden

Jeder DEA ist auch ein NEA, bei dem jede Menge von Folgezuständen genau ein Element hat. Beide Automatenarten erkennen dieselben Sprachen, siehe Gleichwertigkeit.

ε-NEA

Ein ε-NEA hat zusätzlich Übergänge, die kein Zeichen lesen. Sie heißen ε-Übergänge und lassen den Automaten den Zustand wechseln, ohne dass das Wort weitergelesen wird. Die Übergangsfunktion lautet:

[math]\displaystyle{ \delta: Q \times (\Sigma \cup \{\varepsilon\}) \to P(Q) }[/math]

In der Tabelle steht für die ε-Übergänge eine eigene Spalte ε. Jeder ε-NEA lässt sich in einen NEA ohne ε-Übergänge und in einen DEA umwandeln, die dieselbe Sprache erkennen, siehe Umwandlung eines ε-NEA.

ε-Abschluss

Der ε-Abschluss [math]\displaystyle{ E(q) }[/math] enthält den Zustand [math]\displaystyle{ q }[/math] und alle Zustände, die von [math]\displaystyle{ q }[/math] nur über ε-Übergänge erreichbar sind. Mehrere ε-Übergänge hintereinander sind erlaubt. Für eine Menge [math]\displaystyle{ S }[/math] von Zuständen ist [math]\displaystyle{ E(S) }[/math] die Vereinigung aller [math]\displaystyle{ E(q) }[/math] mit [math]\displaystyle{ q \in S }[/math].

Beispiele

Spam-Filter als NEA modellieren

Spam-Filter als NEA

Ein Spam-Filter erkennt E-Mails, die die Zeichenfolge UML enthalten. Das Alphabet ist [math]\displaystyle{ \Sigma = \{U, M, L, x\} }[/math], dabei steht x für jedes andere Zeichen.

Die Idee des Automaten:

  • q0 läuft über alle Zeichen hinweg und bleibt dabei in q0. Bei jedem U vermutet er zusätzlich einen Anfang von UML und öffnet einen zweiten Weg nach q1.
  • q1 wartet auf M, q2 wartet auf L. Jedes andere Zeichen lässt den Pfad dort abbrechen.
  • q3 ist der Endzustand. Er bleibt bei jedem Zeichen in q3.

Bei U in q0 gibt es zwei Folgezustände: [math]\displaystyle{ \delta(q0, U) = \{q0, q1\} }[/math]. Das ist der Nichtdeterminismus. Die Übergangstabelle zeigt alle Übergänge:

Zustand U M L x
→ q0 {q0, q1} {q0} {q0} {q0}
q1 – {q2} – –
q2 – – {q3} –
* q3 {q3} {q3} {q3} {q3}

Die Nachricht xUML hat zwei Pfade:

  • q0 –x→ q0 –U→ q0 –M→ q0 –L→ q0 (kein Endzustand)
  • q0 –x→ q0 –U→ q1 –M→ q2 –L→ q3 (akzeptiert)

Der zweite Pfad liest das ganze Wort und endet im Endzustand q3. Mindestens ein Pfad ist erfolgreich, daher wird xUML akzeptiert. Der erste Pfad endet in q0 und spricht nicht dagegen.

ε-Abschluss bestimmen

ε-NEA für Wörter nur aus a oder nur aus b

Der ε-NEA hat die Zustände q0, q1 und q2 über dem Alphabet [math]\displaystyle{ \Sigma = \{a, b\} }[/math]. Von q0 führen zwei ε-Übergänge nach q1 und nach q2. Die Zustände q1 und q2 sind Endzustände. q1 liest beliebig viele a, q2 liest beliebig viele b.

Zustand a b ε
→ q0 – – {q1, q2}
* q1 {q1} – –
* q2 – {q2} –

Die ε-Abschlüsse:

  • [math]\displaystyle{ E(q0) = \{q0, q1, q2\} }[/math]: q0 selbst, dazu q1 und q2 über je einen ε-Übergang.
  • [math]\displaystyle{ E(q1) = \{q1\} }[/math]: Von q1 geht kein ε-Übergang aus.
  • [math]\displaystyle{ E(q2) = \{q2\} }[/math]: Von q2 geht kein ε-Übergang aus.

Der Automat akzeptiert Wörter, die nur aus a oder nur aus b bestehen. Auch das leere Wort wird akzeptiert: Ohne ein Zeichen zu lesen, erreicht der Automat über einen ε-Übergang den Endzustand q1 oder q2.