Epsilon-NEA

ε-Übergänge sind Zustandsübergänge ohne Eingabe, denn ε bedeutet, dass man keine Eingabe tätigt.

Umwandlung eines ε-NEA in einen NEA

Zur anschaulichen Erklärung, wie man einen ε-NEA in einen NEA umwandelt nehmen wir folgendes Beispiel: Gegeben sei der reguläre Ausdruck 0ⁱ 1^j 2^k ( i,j,k >= 0 ). Damit sind zum Beispiel folgende Worte möglich : 001122 / 000 / ε / 02 / 1111

In einem Zustandsgraphen sähe das dann so aus:

Man könnte zwar auch basteln, wie ein NEA/DEA aussähe, jedoch ist die ε-Variante einfacher.

Umwandlungsmöglichkeiten

Es gibt nun 2 Möglichkeiten um diesen ε-NEA in einen NEA umzuformen.

Variante 1

Bei dieser Variante benutzt man eine Übergangstabelle, in die man zunächst alle Zustände, ihre Eingabemöglichkeiten und die daraus resultierenden Zustände einträgt. Diese sähe nach obigem Beispiel wie folgt aus:

   |      0      |      1      |      2     
---|-------------|-------------|------------
s0 |  s0,s1,s2   |    s1,s2    |     s2     
---|-------------|-------------|------------
s1 |             |    s1,s2    |     s2     
---|-------------|-------------|------------
s2 |             |             |     s2     

Nun benennt man alle neuen Zustände nach belieben.

s0,s1,s2 benennen wir um in "zA". s1,s2 benennen wir um in "zB". s2 benennen wir um in "zC".

s2 ist ein Endzustand. Hier zA, zB und zC auch zu Endzuständen, da alle Zustandsmengen die mind. einen Endzustand enthalten somit auch zu Endzuständen werden.

Die Übergangstabelle wandelt man dann in einen NEA-Graphen um.

Variante 2

Die 2. Variante übergeht die Übergangstabelle und man wandelt den ε-NEA ohne diesen Zwischenschritt in einen NEA um.

Statt dessen geht man in 3 Schritten vor:

1. ε-Zyklen zusammenfassen
2. ε-Schlingen beseitigen
3. "Durchschalten"

1. ε-Zyklen zusammenfassen

Indem man mind. 2 Zustände, welche in beide Richtungen durch ε-Übergänge verbunden sind, zu einem zusammenfasst, lassen sich diese ε-Zyklen entfernen.

2. ε-Schlingen beseitigen

Als ε-Schlingen bezeichnet man ε-Übergänge, die auf denselben Zustand zeigen. Diese können einfach entfernt werden.

3. "Durchschalten"

Hierbei werden ε-Übergänge ersetzt wie im folgenden Grafen.

Man kann also alle Transitionen ε-x-ε, ε-x und x-ε durch eine Transition x ersetzen.

Anschließend benennt man noch die neuen Zustände. Man erhält den selben Grafen wie bei Variante 1.

Beispiel für Variante 2

Ausgangsgraph

1. Schritt: ε-Zyklen zusammenfassen

2. Schritt: ε-Schlingen weglassen (hier lediglich bei S1) und 3. Schritt: Durchschalten

Wenn man zum Vergleich das 2. Beispiel Bild betrachtet: Man kann z.B. erst ε und dann a eingeben. So kommt man von s0 zu s3. Daraus entsteht dann der neue Übergang.