| Autor |
  Schnittautomat |
|
civilengineer
Aktiv 
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
 |  Themenstart: 2023-01-31
|
Für zwei vorgegebenen Sprachen versuche ich seit heute Morgen einen Schnittautomaten zu generieren. Ich bin einem YouTube-Video (https://youtu.be/QSpErcGyXPM) gefolgt, wo diese Konstruktion erläutert wird. Allerdings überzeugt der Schnittautomat nicht wirklich und ich bin mir unsicher, ob das so korrekt ist? Ich meine die gestrichelten Linie sollten durchzogen werden, weil es sich um akzeptierende Zustände handelt, wenn einer von den geschnittenen Zuständen akzeptierend ist? w[i,j] ist ein Teilwort von w von dem i-ten bis zu dem j-ten Buchstaben von w.
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230131_184224.jpg
In der Musterlösung der Aufgabe wird nicht erläutert, wie sie auf das Ergebnis kommen.
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_Screenshot_20230131_190646_Adobe_Acrobat.jpg
Im Skript stehen jede Menge Märchen über alles Mögliche!
Danke für die Info im Voraus!
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
|
\quoteon(2023-01-31 18:45 - civilengineer im Themenstart)
Für zwei vorgegebenen Sprachen versuche ich seit heute Morgen einen Schnittautomaten zu generieren. Ich bin einem YouTube-Video (https://youtu.be/QSpErcGyXPM) gefolgt, wo diese Konstruktion erläutert wird. Allerdings überzeugt der Schnittautomat nicht wirklich und ich bin mir unsicher, ob das so korrekt ist? Ich meine die gestrichelten Linie sollten durchzogen werden, weil es sich um akzeptierende Zustände handelt, wenn einer von den geschnittenen Zuständen akzeptierend ist? w[i,j] ist ein Teilwort von w von dem i-ten bis zu dem j-ten Buchstaben von w.
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230131_184224.jpg
In der Musterlösung der Aufgabe wird nicht erläutert, wie sie auf das Ergebnis kommen.
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_Screenshot_20230131_190646_Adobe_Acrobat.jpg
Im Skript stehen jede Menge Märchen über alles Mögliche!
Danke für die Info im Voraus!
EDIT: nach den Erläuterungen von https://youtu.be/IcJvvt1IBNU müsste der Automat ohne die gestrichelten Kreise richtig sein. 🤔
Viele Grüße
CE
\quoteoff
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.2, vom Themenstarter, eingetragen 2023-01-31
|
\quoteon(2023-01-31 19:59 - civilengineer in Beitrag No. 1)
\quoteon(2023-01-31 18:45 - civilengineer im Themenstart)
Für zwei vorgegebenen Sprachen versuche ich seit heute Morgen einen Schnittautomaten zu generieren. Ich bin einem YouTube-Video (https://youtu.be/QSpErcGyXPM) gefolgt, wo diese Konstruktion erläutert wird. Allerdings überzeugt der Schnittautomat nicht wirklich und ich bin mir unsicher, ob das so korrekt ist? Ich meine die gestrichelten Linie sollten durchzogen werden, weil es sich um akzeptierende Zustände handelt, wenn einer von den geschnittenen Zuständen akzeptierend ist? w[i,j] ist ein Teilwort von w von dem i-ten bis zu dem j-ten Buchstaben von w.
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230131_184224.jpg
In der Musterlösung der Aufgabe wird nicht erläutert, wie sie auf das Ergebnis kommen.
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_Screenshot_20230131_190646_Adobe_Acrobat.jpg
Im Skript stehen jede Menge Märchen über alles Mögliche!
Danke für die Info im Voraus!
\quoteoff
\quoteoff
EDIT: nach den Erläuterungen von https://youtu.be/IcJvvt1IBNU müsste mein von Hand gezeichneter Automat ohne die gestrichelten Kreise richtig sein. 🤔 Aber dann frage ich mich, wenn man im Zustand 0A2B landet und zwei Nullen hintereinander liest, dann müsste dieses Wort akzeptiert werden? Ach ge, passt wieder nicht, es muss sowohl das eine als auch das andere gelten, passt schon, müsste jetzt so passen, ge?
\quoteon
Viele Grüße
CE
\quoteoff
|
Profil
|
thureduehrsen
Senior 
Dabei seit: 13.11.2007
Mitteilungen: 1415
Wohnort: Kiel, Deutschland
 | Beitrag No.3, eingetragen 2023-01-31
|
\quoteon(2023-01-31 18:45 - civilengineer im Themenstart)
In der Musterlösung der Aufgabe wird nicht erläutert, wie sie auf das Ergebnis kommen.
\quoteoff
Oh doch.
\quoteon 
\quoteoff
Ich habe selten eine so klare Beschreibung gelesen, warum der Automat genau das tut, was er soll.
Wo genau bleibst du hängen?
mfg
thureduehrsen
[Die Antwort wurde vor Beitrag No.1 begonnen.]
|
Profil
|
thureduehrsen
Senior 
Dabei seit: 13.11.2007
Mitteilungen: 1415
Wohnort: Kiel, Deutschland
| Beitrag No.4, eingetragen 2023-01-31
|
\quoteon(2023-01-31 20:01 - civilengineer in Beitrag No. 2)
EDIT: [...] müsste mein von Hand gezeichneter Automat ohne die gestrichelten Kreise richtig sein.
\quoteoff
Dein von Hand gezeichneter Automat hat keinen Startzustand.
mfg
thureduehrsen
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.5, vom Themenstarter, eingetragen 2023-01-31
|
Erläuterung schön und gut, wenn sie das Ergebnis hinmalen und darüber philosophieren. Ich muss aber selbst erstmal drauf kommen, dass das Ding zeichnerisch so ausschaut. Um ehrlich zu sein habe ich genau aus diesem Grund die Begründung, warum das Ergebnis das Ergebnis ist, nicht gelesen...
EDIT: Ok, 0A0B ist der Startzustand von meinem Automaten. Ist er so korrekt? Danke für deine Unterstützung.
[Die Antwort wurde nach Beitrag No.3 begonnen.]
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1415
Wohnort: Kiel, Deutschland
| Beitrag No.6, eingetragen 2023-01-31
|
Ich gehe mal davon aus, dass die Autoren der Musterlösung hier nicht mit dem Produktautomaten angefangen haben und ihn minimiert haben, sondern den Automaten "per Hand" aufgebaut haben.
Zuerst haben sie die gerade Anzahl der Nullen durch die Zustände 1 und 4 sichergestellt.
Dann haben sie ausgeschlossen, dass das Teilwort 110 vorkommt mittels der Zustände 2, 3, 6. Der Zustand 6 ist der Fehlerzustand.
Und so weiter. Intuition und Herumprobieren hilft hier viel.
mfg
thureduehrsen
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1415
Wohnort: Kiel, Deutschland
| Beitrag No.7, eingetragen 2023-01-31
|
\quoteon(2023-01-31 20:09 - civilengineer in Beitrag No. 5)
EDIT: Ok, 0A0B ist der Startzustand von meinem Automaten. Ist er so korrekt? Danke für deine Unterstützung.
\quoteoff
Dein Automat weist das Wort 1010 zurück, das aber in L enthalten ist: die Anzahl der Nullen ist gerade, und das Teilwort 110 taucht nicht auf.
Dein Automat gelangt bei der Verarbeitung des Wortes in den Zustand 0A2B, den du nichtakzeptierend gesetzt hast.
mfg
thureduehrsen
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.8, vom Themenstarter, eingetragen 2023-01-31
|
In der Prüfung gibt es leider keine Zeit, um Sachen mal zu probieren...
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.9, vom Themenstarter, eingetragen 2023-01-31
|
Obwohl ich die "Produktkonstruktion" richtig ausgeführt habe, ist das Ergebnis nicht richtig...
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.10, vom Themenstarter, eingetragen 2023-01-31
|
Ich habe einen Automaten mit 3 Zuständen und durchs Knobeln hingemalt, der eine gerade Anzahl an Nullen akzeptiert und das Teilwort 110 nicht akzeptiert. Ist der so in Ordnung?!
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230131_212507.png
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1415
Wohnort: Kiel, Deutschland
| Beitrag No.11, eingetragen 2023-02-01
|
Betrachte mal das Wort 1100.
mfg
thureduehrsen
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.12, vom Themenstarter, eingetragen 2023-02-01
|
\quoteon(2023-02-01 01:15 - thureduehrsen in Beitrag No. 11)
Betrachte mal das Wort 1100.
mfg
thureduehrsen
\quoteoff
wird akzeptiert, wobei 1100 das Teilwort 110 enthält...
|
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-01-31 18:45 - civilengineer im Themenstart)
Für zwei vorgegebenen Sprachen versuche ich seit heute Morgen einen Schnittautomaten zu generieren. Ich bin einem YouTube-Video (https://youtu.be/QSpErcGyXPM) gefolgt, wo diese Konstruktion erläutert wird. Allerdings überzeugt der Schnittautomat nicht wirklich und ich bin mir unsicher, ob das so korrekt ist? Ich meine die gestrichelten Linie sollten durchzogen werden, weil es sich um akzeptierende Zustände handelt, wenn einer von den geschnittenen Zuständen akzeptierend ist? w[i,j] ist ein Teilwort von w von dem i-ten bis zu dem j-ten Buchstaben von w.
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230131_184224.jpg
...
\quoteoff
Warum funktioniert diese Schnittkonstruktion nicht? Warum akzeptiert das Ding 1010 nicht?! 🤔 Die Schnittkonstruktion wird z. B. auch hier beschrieben. Ich meine die Einzelautomaten scheinen für sich zu stimmen...🤔
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2710
 | Beitrag No.14, eingetragen 2023-02-01
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}
\newcommand{\monus}{\mathbin {∸}}\)
Der Automat für $L_B$ ist falsch. Er akzeptiert 11 nicht. 1010 auch nicht.\(\endgroup\)
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.15, vom Themenstarter, eingetragen 2023-02-01
|
\quoteon(2023-02-01 22:23 - tactac in Beitrag No. 14)
Der Automat für $L_B$ ist falsch. Er akzeptiert 11 nicht. 1010 auch nicht.
\quoteoff
Danke für den Tipp, ich gucke es mir morgen nochmal in Ruhe an und versuche es nochmal richtig zu lösen. Ich denke, ich kriege es beim nächsten Versuch hin.
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.16, vom Themenstarter, eingetragen 2023-02-02
|
\quoteon(2023-02-01 22:23 - tactac in Beitrag No. 14)
Der Automat für $L_B$ ist falsch. Er akzeptiert 11 nicht. 1010 auch nicht.
\quoteoff
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230202_200323.jpg
Passt es jetzt so?...
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1415
Wohnort: Kiel, Deutschland
| Beitrag No.17, eingetragen 2023-02-02
|
\quoteon(2023-02-02 20:05 - civilengineer in Beitrag No. 16)
Passt es jetzt so?...
\quoteoff
Nein.
mfg
thureduehrsen
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.18, vom Themenstarter, eingetragen 2023-02-02
|
\quoteon(2023-02-02 20:47 - thureduehrsen in Beitrag No. 17)
\quoteon(2023-02-02 20:05 - civilengineer in Beitrag No. 16)
Passt es jetzt so?...
\quoteoff
Nein.
mfg
thureduehrsen
\quoteoff
Ok, warum? Ich denke, der Automat für \(L_B\) ist immer noch falsch, weil er 1010 immer noch nicht akzeptiert...
Eine Frage: wie wird ein Automat konstruiert, der Teilwörter 110 nicht akzeptiert? Also gedanklich erstmal?!...
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2710
| Beitrag No.19, eingetragen 2023-02-02
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}
\newcommand{\monus}{\mathbin {∸}}\)
\quoteon(2023-02-02 21:17 - civilengineer in Beitrag No. 18)
Eine Frage: wie wird ein Automat konstruiert, der Teilwörter 110 nicht akzeptiert? Also gedanklich erstmal?!...
\quoteoff
Hier funktioniert ganz gut: konstruiere erstmal so weit, dass du etwas hast, das das leere Wort, $1$ und $11$ akzeptiert, aber $110$ nicht akzeptiert. (Warum gerade diese Worte? Nun, das sind alle Präfixe von $110$; den Zuständen würde ich übrigens auch genau diese Worte als Namen geben.) Dann fehlende Pfeile und ggf. Zustände ergänzen.\(\endgroup\)
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1415
Wohnort: Kiel, Deutschland
| Beitrag No.20, eingetragen 2023-02-02
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
\quoteon(2023-02-02 21:17 - civilengineer in Beitrag No. 18)
Wie wird ein Automat konstruiert, der Teilwörter 110 nicht akzeptiert? Also gedanklich erstmal?!...
\quoteoff
Man kann zum Beispiel zunächst einen Automaten konstruieren, der die Sprache
\[
\{w\in\{0,1\}^\ast: w\text{ enthält das Teilwort \(1\,1\,0\)}\}
\]
akzeptiert und dann zum Komplement übergehen.
Übungsaufgabe: Führe das mal durch. Im Detail. Mit allen Zwischenschritten. Gerne in Tabellenform, so wie hier.
mfg
thureduehrsen
[Die Antwort wurde nach Beitrag No.18 begonnen.]\(\endgroup\)
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.21, vom Themenstarter, eingetragen 2023-02-02
|
Ich glaube du meinst https://youtu.be/SIrGv8ZnIMo
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1415
Wohnort: Kiel, Deutschland
| Beitrag No.22, eingetragen 2023-02-02
|
\quoteon(2023-02-02 21:17 - civilengineer in Beitrag No. 18)
\quoteon(2023-02-02 20:47 - thureduehrsen in Beitrag No. 17)
\quoteon(2023-02-02 20:05 - civilengineer in Beitrag No. 16)
Passt es jetzt so?...
\quoteoff
Nein.
mfg
thureduehrsen
\quoteoff
Ok, warum?
\quoteoff
In dem Graphen in Beitrag No. 16 fehlt der Startzustand (also: ist kein Zustand als Startzustand ausgezeichnet).
mfg
thureduehrsen
[Die Antwort wurde nach Beitrag No.20 begonnen.]
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.23, vom Themenstarter, eingetragen 2023-02-02
|
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230202_220238.jpg
Beim 110-Akzeptierer sehe ich gerade, dass er auch 1010 akzeptieren würde, was er nicht darf, ich muss es mir anders überlegen...
[Die Antwort wurde nach Beitrag No.21 begonnen.]
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.24, vom Themenstarter, eingetragen 2023-02-02
|
\quoteon(2023-02-02 21:40 - thureduehrsen in Beitrag No. 22)
\quoteon(2023-02-02 21:17 - civilengineer in Beitrag No. 18)
\quoteon(2023-02-02 20:47 - thureduehrsen in Beitrag No. 17)
\quoteon(2023-02-02 20:05 - civilengineer in Beitrag No. 16)
Passt es jetzt so?...
\quoteoff
Nein.
mfg
thureduehrsen
\quoteoff
Ok, warum?
\quoteoff
In dem Graphen in Beitrag No. 16 fehlt der Startzustand (also: ist kein Zustand als Startzustand ausgezeichnet).
mfg
thureduehrsen
[Die Antwort wurde nach Beitrag No.20 begonnen.]
\quoteoff
Der erste oben links.
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.25, vom Themenstarter, eingetragen 2023-02-02
|
\quoteon(2023-02-02 21:38 - thureduehrsen in Beitrag No. 20)
\quoteon(2023-02-02 21:17 - civilengineer in Beitrag No. 18)
Wie wird ein Automat konstruiert, der Teilwörter 110 nicht akzeptiert? Also gedanklich erstmal?!...
\quoteoff
Man kann zum Beispiel zunächst einen Automaten konstruieren, der die Sprache
\[
\{w\in\{0,1\}^\ast: w\text{ enthält das Teilwort \(1\,1\,0\)}\}
\]
akzeptiert und dann zum Komplement übergehen.
Übungsaufgabe: Führe das mal durch. Im Detail. Mit allen Zwischenschritten. Gerne in Tabellenform, so wie hier.
mfg
thureduehrsen
[Die Antwort wurde nach Beitrag No.18 begonnen.]
\quoteoff
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230202_221414.jpg
?
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2710
| Beitrag No.26, eingetragen 2023-02-02
|
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]}
\newcommand{\name}[1]{\ulcorner#1\urcorner}
\newcommand{\upamp}{\mathbin {⅋}}
\newcommand{\monus}{\mathbin {∸}}\)
Der 110-Verwerfer stimmt jetzt. Hier mal in TikZ:
$
\tikzset{->}
\begin{tikzpicture}
\node[state, initial, accepting] at (2,1) (e) {$\varepsilon$};
\node[state, accepting] at (4,1) (1) {$1$};
\node[state, accepting] at (6,1) (11) {$11$};
\node[state] at (8,1) (110) {$110$};
\draw (e) edge[loop above] node{0} (e);
\draw (e) edge[bend left, above] node{1} (1);
\draw (1) edge[bend left, below] node{0} (e);
\draw (1) edge[above] node{1} (11);
\draw (11) edge[loop above] node{1} (11);
\draw (11) edge[above] node{0} (110);
\draw (110) edge[loop above] node{0,1} (110);
\end{tikzpicture}
$\(\endgroup\)
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
|  Beitrag No.27, vom Themenstarter, eingetragen 2023-02-02
|
Danke! 27 Beiträge. Ende Gelände. Aus die Maus. Aus, Äpfel, Amen.
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2710
| Beitrag No.28, eingetragen 2023-02-02
|
Musst du nicht noch den Schnittautomaten prüfen? 😉
|
Profil
|
civilengineer
Aktiv
Dabei seit: 25.05.2011
Mitteilungen: 1805
Wohnort: Bayern, München
| Beitrag No.29, vom Themenstarter, eingetragen 2023-02-03
|
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230203_115548.jpg
Ist es irgendwie möglich direkt mit dem Ergebnis-Automaten anzufangen und ihn einfach loszuzeichnen? Sagen wir, wir fangen z. B. so an:
https://matheplanet.com/matheplanet/nuke/html/uploads/c/31462_20230203_124831.jpg
Danach finde ich es schwierig, zu überlegen, wohin die fehlenden möglichen Eingaben für jeden Zustand führen sollten... Oder ist hier ganz anders zu denken/überlegen?
?
|
Profil
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
