| |
| Autor |
  DEA aus regulärem Ausdruck ableiten |
|
civilengineer
Aktiv 
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
 |  Themenstart: 2023-01-31
|
Mein Lösungsversuch orientiert sich in etwa am beschriebenen Verfahren auf der Webseite (https://www.javatpoint.com/automata-conversion-of-re-to-fa) :
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230131_214221.jpg
In der Musterlösung wird die folgende Lösung ohne Begründung und ohne Konstruktionsmethode gegeben:
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_Screenshot_20230131_214207_Adobe_Acrobat.jpg
Ich verstehe die Musterlösung nicht und sie ist mir auch egal. Ich würde bloß gerne wissen, ob das die einfachste Methode ist, die es gibt und ob mein Ergebnis in Ordnung ist?
Danke für die Unterstützung im Voraus.
EDIT: nachdem ich dieses Video https://youtu.be/62JAy4oH6lU und weitere Videos vom selben Kanal zu diesem Thema entdeckt habe, denke ich, dass (a*+b)ca* = {c,ac, aac, ca, caa, aca, aaaaaacaa, bc, bca, bcaaaaa, ...} durch den folgenden Automaten akzeptiert wird:
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230131_224809.jpg
Korrekt?
Eine Frage: wie ist das Pluszeichen (Vereinigung?!) in einem regulären Ausdruck genau zu verstehen? Ein "Entweder Oder", stimmts?
Viele Grüße
CE
|
 Profil
|
civilengineer
Aktiv 
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.1, vom Themenstarter, eingetragen 2023-01-31
|
Scheint zu passen, wenn die restlichen Übergänge eingezeichnet worden wären und in einen Fehlerzustand überführen würden, eine Bestätigung von einem erfahrenen Kollegen wäre trotzdem cool. Danke.
|
Profil
|
tactac
Senior 
Dabei seit: 15.10.2014
Mitteilungen: 2712
 | Beitrag No.2, eingetragen 2023-02-01
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}
\newcommand{\monus}{\mathbin {∸}}\)
Dein Automat akzeptiert auch $abc$. Das darf er nicht.\(\endgroup\)
|
Profil
|
thureduehrsen
Senior 
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
 | Beitrag No.3, eingetragen 2023-02-01
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Im Themenstart hast du die ersten 5 Schritte der kanonischen Überführung von einem regulären Ausdruck zu einem DEA mustergültig ausgeführt.
Von da aus kannst du doch einfach weitermachen?
\quoteon(2023-01-31 21:48 - civilengineer im Themenstart)
Eine Frage: wie ist das Pluszeichen (Vereinigung?!) in einem regulären Ausdruck genau zu verstehen? Ein "Entweder Oder", stimmts?
\quoteoff
Nein. Das Pluszeichen steht für ein einschließendes Oder.
Beispielsweise gilt
\[
L(a\,(b+b)) = L(a\,b) = \{a\,b\}
\]
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.4, vom Themenstarter, eingetragen 2023-02-01
|
\quoteon(2023-02-01 01:26 - thureduehrsen in Beitrag No. 3)
Im Themenstart hast du die ersten 5 Schritte der kanonischen Überführung von einem regulären Ausdruck zu einem DEA mustergültig ausgeführt.
Von da aus kannst du doch einfach weitermachen?
\quoteoff
Ich weiß nicht, wie es ab dem 5. Schritt weitergehen soll.
\quoteon
\quoteon(2023-01-31 21:48 - civilengineer im Themenstart)
Eine Frage: wie ist das Pluszeichen (Vereinigung?!) in einem regulären Ausdruck genau zu verstehen? Ein "Entweder Oder", stimmts?
\quoteoff
Nein. Das Pluszeichen steht für ein einschließendes Oder.
Beispielsweise gilt
\[
L(a\,(b+b)) = L(a\,b) = \{a\,b\}
\]
\quoteoff
Ja, ok, in der Sprache heißt es eine Vereinigung, aber im Automaten sind es zwei verschiedene "Wege"... 🤔
\quoteon
mfg
thureduehrsen
\quoteoff
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.5, eingetragen 2023-02-01
|
\quoteon(2023-02-01 07:21 - civilengineer in Beitrag No. 4)
Ich weiß nicht, wie es ab dem 5. Schritt weitergehen soll.
\quoteoff
Tue doch einmal so, als hätte ich keine Ahnung und erkläre mir, was du beim Übergang von 4 zu 5 getan hast.
Vielleicht ungefähr so ausführlich wie hier.
mfg
thureduehrsen
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.6, vom Themenstarter, eingetragen 2023-02-01
|
Aus einem NEA einen DEA gemacht. Mit Fehlerzustand. Eigentlich müsste die Aufgabe an dieser Stelle enden. Ich bin mir aber nicht mehr so sicher, ob und warum das Ergebnis im Schritt 5 so (nicht) passt...
hier ist es ausführlicher beschrieben.
Ich muss mir mal diese Konstruktion nochmal in Ruhe ansehen.
Nach dem Lesen (über die Potenzmengenkonstruktion) glaube ich, dass sowohl der obige DEA im Themenstart, der im 5. Schritt ermittelt wurde, als auch der folgende DEA korrekt sind, stimmts?...
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230201_174524.jpg
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.7, eingetragen 2023-02-01
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
\quoteon(2023-02-01 17:01 - civilengineer in Beitrag No. 6)
glaube ich, dass sowohl der obige DEA im Themenstart, der im 5. Schritt ermittelt wurde, als auch der folgende DEA korrekt sind
\quoteoff
Der DEA, der hier im 5. Schritt steht,
ist nicht korrekt, denn er erkennt auch das Wort \(b\,b\,c\), das nicht zur Sprache \(L((a^\ast+b)ca^\ast)\) gehört.
Der DEA, der hier im 3. Schritt steht,
ist korrekt, und seine Konstruktion ist auch klarer erkennbar. Er dürfte sogar minimal für diese Sprache sein.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.8, vom Themenstarter, eingetragen 2023-02-01
|
Danke für die Info. Aber dann frage ich mich, wie mit derselben Konstruktionsmethode einmal ein richtiger (im 3. Schritt) und ein zweites Mal ein falscher Automat (im 5. Schritt) resultieren konnten. Fällt dir vlt. etwas bei der Konstruktion im Themenstart auf, das bei der Ermittlung vom DEA nicht richtig ist?
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.9, eingetragen 2023-02-01
|
Es könnte sein, dass ich etwas voreilig war mit meiner Aussage, dass du die Schritte fehlerfrei abgearbeitet hast bei dieser Konstruktion.
Erkläre mir mal den Übergang von Schritt 3 nach Schritt 4.
Insbesondere: warum ist der Startzustand akzeptierend?
mfg
thureduehrsen
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.10, vom Themenstarter, eingetragen 2023-02-01
|
Der Übergang ist so gedacht, dass man gar kein a also das leere Wort oder mehrere as eingeben darf. Es kann sein, dass der Übergang vom Schritt 3 zum Schritt 4 falsch ist und dass man die kleensche Hülle von a anders modellieren sollte. Ich weiß es nicht. Der Startzustand ist verwerfend.
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.11, eingetragen 2023-02-01
|
\quoteon(2023-02-01 18:38 - civilengineer in Beitrag No. 10)
Der Startzustand ist verwerfend.
\quoteoff
Warum hat er dann einen Doppelkreis?
mfg
thureduehrsen
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.12, eingetragen 2023-02-01
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
\quoteon(2023-02-01 18:38 - civilengineer in Beitrag No. 10)
und dass man die kleensche Hülle von a anders modellieren sollte
\quoteoff
Versuche es mal so:
$
\begin{tikzpicture}
[
->, >=stealth', shorten >=1pt,
auto,node distance=21mm,
thick,
]
\node[initial,state] (q0) {};
\node[state] (q1) [right of=q0] {};
\node[state] (q2) [right of=q1] {};
\node[accepting,state] (q3) [right of=q2] {};
\path[every node/.style={font=\small},align=center]
(q0) edge [above] node {$\varepsilon$} (q1)
(q1) edge [above] node {a} (q2)
(q2) edge [above] node {$\varepsilon$} (q3)
(q0) edge [above,bend left] node {$\varepsilon$} (q3)
(q2) edge [below,bend left] node {$\varepsilon$} (q1)
;
\end{tikzpicture}
$
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.13, vom Themenstarter, eingetragen 2023-02-01
|
\quoteon(2023-02-01 18:44 - thureduehrsen in Beitrag No. 11)
\quoteon(2023-02-01 18:38 - civilengineer in Beitrag No. 10)
Der Startzustand ist verwerfend.
\quoteoff
Warum hat er dann einen Doppelkreis?
mfg
thureduehrsen
\quoteoff
Der Zustand 0 im Schritt 4 ist der Startzustand und hat keinen Doppelkreis?
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.14, eingetragen 2023-02-01
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Ach, das ist eine Null und kein Kreis? Sorry...
Aber modelliere den Kleene-Stern trotzdem mal gemäß meinem Vorschlag.
Denn dein Automat in Schritt 4 akzeptiert das Wort \(b\,a\,c\), das er nicht akzeptieren soll.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.15, vom Themenstarter, eingetragen 2023-02-01
|
Danke dir. Ich denke, der Fehler beim Übergang von Schritt 3 zum Schritt 4 wurde zweimal gemacht (zwischen Zustand 0 und 1 sowie zwischen Zustand 2 und 3 jeweils bei a*), die a Schleife hätte logischerweise ein Zustand früher verschoben werden sollen (ist vermutlich egal, oder?!). Ich weiß nicht, ob die folgende Korrektur passt, aber ich hoffe es. Was meinst du?
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230201_222146.jpg
Das ist im Prinzip dasselbe Ergebnis wie mit den 5 Schritten...
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.16, vom Themenstarter, eingetragen 2023-02-01
|
\quoteon(2023-02-01 00:21 - tactac in Beitrag No. 2)
Dein Automat akzeptiert auch $abc$. Das darf er nicht.
\quoteoff
Jeder Ergebnis-Automat bisher akzeptiert abc... Außer dem Automaten aus der Musterlösung, aber bei dem wird nicht erklärt, wie er abgeleitet wird...
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.17, eingetragen 2023-02-02
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
\quoteon(2023-02-01 22:25 - civilengineer in Beitrag No. 15)
\quoteoff
Hier akzeptiert der Automat 3 das Wort \(a\,b\,c\) nicht, aber der Automat 4 tut es. Also ist die Umformung falsch.
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.18, eingetragen 2023-02-02
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Ich spendiere noch mal ein paar Zwischenschritte.
|
$
\begin{tikzpicture}
[
->, >=stealth', shorten >=1pt,
auto,node distance=40mm,
thick,
]
\node[state,initial] (q0) {\(q_0\)};
\node[state,accepting] (q1) [right of=q0] {\(q_1\)};
\path (q0) edge node {$(a^\ast+b)\,c\,a^\ast$} (q1)
;
\end{tikzpicture}
$
|
|
Anfangszustand: einzige Kante mit dem gesamten regulären Ausdruck beschriftet |
|
|
|
|
$
\begin{tikzpicture}
[
->, >=stealth', shorten >=1pt,
auto,node distance=25mm,
thick,
]
\node[state,initial] (q0) {\(q_0\)};
\node[state] (q1) [right of=q0] {\(q_1\)};
\node[state,accepting] (q2) [right of=q1] {\(q_2\)};
\path (q0) edge node {$(a^\ast+b)$} (q1)
(q1) edge node {$c\,a^\ast$} (q2)
;
\end{tikzpicture}
$
|
|
erste Auftrennung bei der Konkatenation |
|
|
|
|
$
\begin{tikzpicture}
[
->, >=stealth', shorten >=1pt,
auto,node distance=25mm,
thick,
]
\node[state,initial] (q0) {\(q_0\)};
\node[state] (q1) [right of=q0] {\(q_1\)};
\node[state,accepting] (q2) [right of=q1] {\(q_2\)};
\path (q0) edge [bend left] node {$a^\ast$} (q1)
(q0) edge [bend right] node {$b$} (q1)
(q1) edge node {$c\,a^\ast$} (q2)
;
\end{tikzpicture}
$
|
|
Auftrennung bei der Alternative: zwei Pfade |
|
|
|
|
$
\begin{tikzpicture}
[
->, >=stealth', shorten >=1pt,
auto,node distance=20mm,
thick,
]
\node[state,initial] (q0) {\(q_0\)};
\node[state] (q1) [right of=q0] {\(q_1\)};
\node[state] (q2) [right of=q1] {\(q_2\)};
\node[state,accepting] (q3) [right of=q2] {\(q_3\)};
\path (q0) edge [bend left] node {$a^\ast$} (q1)
(q0) edge [bend right] node {$b$} (q1)
(q1) edge node {$c$} (q2)
(q2) edge node {$a^\ast$} (q3)
;
\end{tikzpicture}
$
|
|
Zweite Auftrennung bei der Konkatenation |
|
|
|
|
$
\begin{tikzpicture}
[
->, >=stealth', shorten >=1pt,
auto,node distance=20mm,
thick,
]
\node[state,initial] (q0) {\(q_0\)};
\node[state] (q1) [right of=q0] {\(q_1\)};
\node[state] (q2) [right of=q1] {\(q_2\)};
\node[state,accepting] (q3) [right of=q2] {\(q_\)};
\path (q0) edge [bend left] node {$a^\ast$} (q1)
(q0) edge [bend right] node {$b$} (q1)
(q1) edge node {$c$} (q2)
(q2) edge node {$a$} (q3)
(q2) edge [bend left] node {$\varepsilon$} (q3)
(q3) edge [bend left] node {$\varepsilon$} (q2)
;
\end{tikzpicture}
$
|
|
Das hintere Vorkommen von \(a^\ast\) kann einfach umgewandelt werden, da hier keine Alternative zu berücksichtigen ist |
|
|
|
|
|
|
mfg
thureduehrsen\(\endgroup\)
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.19, eingetragen 2023-02-02
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Ersetze doch mal (mutatis mutandis) das Vorkommen von \(a^\ast\) zwischen \(q_0\) und \(q_1\) in meinem letzten Automaten durch diese Konstruktion
\quoteon(2023-02-01 19:01 - thureduehrsen in Beitrag No. 12)
$
\begin{tikzpicture}
[
->, >=stealth', shorten >=1pt,
auto,node distance=21mm,
thick,
]
\node[initial,state] (q0) {};
\node[state] (q1) [right of=q0] {};
\node[state] (q2) [right of=q1] {};
\node[accepting,state] (q3) [right of=q2] {};
\path[every node/.style={font=\small},align=center]
(q0) edge [above] node {$\varepsilon$} (q1)
(q1) edge [above] node {a} (q2)
(q2) edge [above] node {$\varepsilon$} (q3)
(q0) edge [above,bend left] node {$\varepsilon$} (q3)
(q2) edge [below,bend left] node {$\varepsilon$} (q1)
;
\end{tikzpicture}
$
\quoteoff
und gib den sich ergebenden Automaten an.
mfg
thureduehrsen
\(\endgroup\)
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.20, vom Themenstarter, eingetragen 2023-02-02
|
\quoteon(2023-02-02 08:36 - thureduehrsen in Beitrag No. 17)
\quoteon(2023-02-01 22:25 - civilengineer in Beitrag No. 15)
\quoteoff
Hier akzeptiert der Automat 3 das Wort \(a\,b\,c\) nicht, aber der Automat 4 tut es. Also ist die Umformung falsch.
mfg
thureduehrsen
\quoteoff
Ja, die Umformung vom Schritt 3 auf Schritt 4 war nicht ganz richtig, aber auch die richtige Umformung, die durch die Anwendung der Potenzmengenkonstruktion entstanden ist, liefert im 4. Schritt einen Automaten, der abc akzeptiert....🤯
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_123.jpg
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.21, vom Themenstarter, eingetragen 2023-02-02
|
\quoteon(2023-02-02 12:52 - thureduehrsen in Beitrag No. 19)
Ersetze doch mal (mutatis mutandis) das Vorkommen von \(a^\ast\) zwischen \(q_0\) und \(q_1\) in meinem letzten Automaten durch diese Konstruktion
\quoteon(2023-02-01 19:01 - thureduehrsen in Beitrag No. 12)
$
\begin{tikzpicture}
[
->, >=stealth', shorten >=1pt,
auto,node distance=21mm,
thick,
]
\node[initial,state] (q0) {};
\node[state] (q1) [right of=q0] {};
\node[state] (q2) [right of=q1] {};
\node[accepting,state] (q3) [right of=q2] {};
\path[every node/.style={font=\small},align=center]
(q0) edge [above] node {$\varepsilon$} (q1)
(q1) edge [above] node {a} (q2)
(q2) edge [above] node {$\varepsilon$} (q3)
(q0) edge [above,bend left] node {$\varepsilon$} (q3)
(q2) edge [below,bend left] node {$\varepsilon$} (q1)
;
\end{tikzpicture}
$
\quoteoff
und gib den sich ergebenden Automaten an.
mfg
thureduehrsen
\quoteoff
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_1.jpg
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_2.jpg
?
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1417
Wohnort: Kiel, Deutschland
| Beitrag No.22, eingetragen 2023-02-04
|
\quoteon(2023-02-02 15:15 - civilengineer in Beitrag No. 21)
\quoteoff
Sieht gut aus. 👍
Der Automat, den du angegeben hast, dürfte sogar minimal sein.
mfg
thureduehrsen
|
Profil
|
civilengineer hat die Antworten auf ihre/seine Frage gesehen.
civilengineer hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
