Epsilon-NDEA zu regulären Ausdrücken: Nach Kleene-Konstruktion, oder ohne

Question

Frage:

ich habe eine Frage zur Erstellung von ε-NDEA's zu regulären Ausdrücken.

Ist meine Annahme richtig, dass bei einem ε-NDEA nicht unbedingt ε-Kanten vorkommen müssen? Laut meinen Musterlösungen müsste meine Aussage so stimmen.

Angenommen, der reguläre Ausdruck wäre folgender:

r1 = a + c(ba)*

Ich würde jetzt ohne nach der Konstruktion von Kleene zu gehen, auf folgenden Automaten kommen:

Text erkannt:

\( a+c(b a)^{*} \)

Aber wenn man nach der Klenee-Konstruktion geht, sieht der Automat dann so aus:

Meine Frage dazu ist: In der Klausur steht nicht explizit, dass man nach der Konstruktion von Klenee gehen muss.

Aber bei einer anderen Musterlösung zu folgendem Ausdruck r = 1+aa*(c(1+bb)c(abc)*)*

ist folgende die Musterlösung, OHNE nach Kleene-Konstruktion zu kommen, also aus dem Kopf:

Wenn ich für diesen regulären Ausdruck aber nach Kleene-Konstruktion gehen würde, würde ich doch auch von S2 zu S1 noch eine Epsilon-Kante ziehen, oder? Und normalerweise nach Konstruktion doch von allen Finalzuständen zu allen Startzuständen.

Wieso unterscheiden sich beide Methoden, sind aber beide gültig? In meinen Vorlesungsunterlagen gibt es nur eine Beispielanleitung an einem sehr einfachen regulären Ausdruck, sonst ist es sehr schwammig. Wenn jemand eine gute Quelle mit auch schwereren Beispielen hätte, wäre ich sehr dankbar.

Liebe Grüße

Answer 1

Ist meine Annahme richtig, dass bei einem ε-NDEA nicht unbedingt ε-Kanten vorkommen müssen?

Ja.

Wenn ich für diesen regulären Ausdruck aber nach Kleene-Konstruktion gehen würde, würde ich doch auch von S2 zu S1 noch eine Epsilon-Kante ziehen, oder?

Kleene-Konstruktion kenne ich nicht. Meinst du die Thomson-Konstruktion?

Wieso unterscheiden sich beide Methoden,

Weil der Kopf nicht so formal vorgeht.

sind aber beide gültig?

Weil der Weg, wie man zu einer Lösung kommt nicht Bestandteil des Endergebnisses ist.

Comments

Das heißt, es gibt mehrere Lösungen, mit jeweils verschiedenen Epsilon-Kanten?

Nein, sorry, bei uns heißt die Formulierung, falls es verlangt wird: "Gehe wie im Beweis des Hauptsatzes von Kleene vor"

---

Ja.

Die ε-Kanten dienen dazu, Teile des Automaten voneinander zu trennen.

Beispiel 1. Ein regulärer Ausdruck für \(a^*(ab)^*\) ist gesucht. Die Teile \(a^*\) und \((ab)^*\) können durch durch folgende Automaten beschrieben werden.

        \(a^*\): \(\rightarrow\stackrel{\stackrel{a}{\curvearrowleft}}{((q_0))}\)

        \((ab)^*\): \(\rightarrow ((q_0))\begin{matrix}\xrightarrow{a}\\\xleftarrow{b}\end{matrix}(q_1)\)

Wenn du jetzt den Endzustand des ersten Automaten mit dem Anfangszustand des zweiten Automaten zusammenlegst, dann beommst du

        \(\rightarrow\stackrel{\stackrel{a}{\curvearrowleft}}{((q_0))}\begin{matrix}\xrightarrow{a}\\\xleftarrow{b}\end{matrix}(q_1)\).

Dieser Automat erkennt aber auch \(abaa\), was nicht auf den regulären Ausdruck passt.

Um das zu verhindern, werden Endzustand des ersten Automaten und Anfangszustand des zweiten Automaten nicht zusammengelegt, sondern mittels einer ε-Kante verbunden:

        \(\rightarrow\stackrel{\stackrel{a}{\curvearrowleft}}{(q_0)}\xrightarrow{\varepsilon}((q_1))\begin{matrix}\xrightarrow{a}\\\xleftarrow{b}\end{matrix}(q_2)\)

Beispiel 2. Ein regulärer Ausdruck für \(a(ab)^*\) ist gesucht. Die Teile \(a\) und \((ab)^*\) können durch durch folgende Automaten beschrieben werden.

        \(a\): \(\rightarrow(q_0)\xrightarrow{a}((q_1))\)   

        \((ab)^*\): \(\rightarrow ((q_0))\begin{matrix}\xrightarrow{a}\\\xleftarrow{b}\end{matrix}(q_1)\)

Hier können Endzustand des ersten Automaten und Startzustand des zweiten Automaten einfach zusammengelegt werden ohne dass eine ε-Kante zur Trennung verwendet wird:

        \(\rightarrow(q_0)\xrightarrow{a}((q_1))\begin{matrix}\xrightarrow{a}\\\xleftarrow{b}\end{matrix}(q_2)\).

Aber natürlich darfst du auch hier eine ε-Kante verwenden:

        \(\rightarrow(q_0)\xrightarrow{a}(q_1)\xrightarrow{\varepsilon}((q_2))\begin{matrix}\xrightarrow{a}\\\xleftarrow{b}\end{matrix}(q_3)\).

---

Dankeschön Oswald, das war sehr hilfreich!

---

Oswald, findest du meine Lösung dann für den regulären Ausdruck

r = a*b* + ac(b*+a) (b+c)* richtig?

Text erkannt:

\( a^{*} b^{*}+a c\left(b^{*}+a\right)(b+c)^{*} \)