Automaten aus gegebener Sprache konstruieren
-
Du weißt schon, wie man mit Binärzahlen rechnet?
n0 = 2*n+0, n1 = 2*n+1
Jetzt kannst du dir eine Tabelle mit 5 Zeilen und 2 Spalten zusammenstellen, um für alle möglichen Rastklassen die Nachfolger zu bilden:
n%5 | n0%5 | n1%5 ------------------ 0 | 1 | 2 | 3 | 4 |Wenn du die Tabelle fertig hast, kannst du sie dann direkt in einen DFA umsetzen
-
Du weißt schon, wie man mit Binärzahlen rechnet?
Hat das obige also gar nicht gestimmt oder wie?
-
Stimmt die Tabelle so:
n%5 | n0%5 | n1%5 ------------------ 0 | 0 | 1 1 | 1 | 2 2 | 2 | 3 3 | 3 | 4 4 | 4 | 0Und wie soll man daraus nun den DEA ablesen können? Ich versteh's einfach nicht.
-
vip@r schrieb:
Du weißt schon, wie man mit Binärzahlen rechnet?
Hat das obige also gar nicht gestimmt oder wie?
Gut erkannt - und das gilt auch für die Tabelle, die du daraus gebildet hast. Wenn du die Tabelle richtig hast, kannst du sie als Übergangstabelle für den Automaten verwenden (erste Spalte: Ausgangpunkt der Kanten, zweite Spalte: Zielpunkt der 0-Kante, dritte Spalte: Zielpunkt der 1-Kante).
-
Und wie berechnet man dann die Tabelle? Wenn du mir das sagen könntest wär ich glücklich
-
vip@r schrieb:
Und wie berechnet man dann die Tabelle? Wenn du mir das sagen könntest wär ich glücklich
Die Rechenvorschriften für die Spalten steht in der ersten Zeile.
Mit n0 meine ich das Wort "n verkettet mit 0".
-
Ich nehme mal nur eine Zeile:
n%5=r=3:
n0=2*n+0: n0%5 = (2*3+0) % 5 = 1
n1=2*n+1: n1%5 = (2*3+1) % 5 = 2(die restlichen Zeilen solltest du selber hinbekommen)
-
Ich komm jetzt auf:
n%5 | n0%5 | n1%5 ------------------ 0 | 0 | 1 1 | 2 | 3 2 | 4 | 0 3 | 1 | 2 4 | 3 | 4Stimmt's jetzt? Wenn ja, wie kann man nun daraus den DEA ablesen?
-
Etwa so:
CStoll schrieb:
(erste Spalte: Ausgangpunkt der Kanten, zweite Spalte: Zielpunkt der 0-Kante, dritte Spalte: Zielpunkt der 1-Kante)
Du machst daraus fünf Zustände und liest aus der Tabelle ab, wohin du mit der Eingabe 0 bzw. 1 gelangen kannst. Start-Zustand und akzeptierender Endzustand ist Zustand 0.
-
vip@r schrieb:
Stimmt's jetzt?
Das bezog sich zwar auf die Tabelle. Aber ob der DEA am Ende stimmt, musst du natürlich selber begründen. Das ist doch Teil der Aufgabe.
-
CStoll schrieb:
Etwa so:
CStoll schrieb:
(erste Spalte: Ausgangpunkt der Kanten, zweite Spalte: Zielpunkt der 0-Kante, dritte Spalte: Zielpunkt der 1-Kante)
Du machst daraus fünf Zustände und liest aus der Tabelle ab, wohin du mit der Eingabe 0 bzw. 1 gelangen kannst. Start-Zustand und akzeptierender Endzustand ist Zustand 0.
So, ich hab jetzt die 5 Zustände dort stehen. Wenn ich nun die erste Zeile in der Tabelle ansehe, dann steht 0 0 1. Die erste 0 ist also quasi der Zustand von dem ich weggeh und die zweite 0 ist der Zustand zu dem ich hin will. Wo aber lese ich ab welche Kante es ist? (also ob's eine 0, oder eine 1, oder ein 0,1-Kante ist)
Kannst du vielleicht noch ein bisschen besser beschreiben? Ich hab das noch nie gemacht! Muss ich zeilenweise vorgehen?
Edit: Ein Bild sagt mehr als tausend Worte. Hier mal mein Versuch deine Beschreibung umzusetzen. Ist das so richtig? http://imageshack.us/photo/my-images/543/33288439.jpg/
-
Ich hab den Graphen jetzt nochmal überprüft und ich denke, der sollte richtig sein.
Ich hab dann hier auch gleich nochmal eine ähnliche Aufgabe. Mir ist die Sprache L gegeben mit der ich einen DEA entwerfen soll:
L = {w in ∑*Bool | w endet auf 01} Gibt's da jetzt auch wieder ein Schema? Oder muss man den DEA durch Überlegungen zusammenbauen?
Hier dann auch gleich mein Vorschlag: http://imageshack.us/photo/my-images/192/25505560.jpg/ Ist das so richtig?
-
vip@r schrieb:
So, ich hab jetzt die 5 Zustände dort stehen. Wenn ich nun die erste Zeile in der Tabelle ansehe, dann steht 0 0 1. Die erste 0 ist also quasi der Zustand von dem ich weggeh und die zweite 0 ist der Zustand zu dem ich hin will. Wo aber lese ich ab welche Kante es ist? (also ob's eine 0, oder eine 1, oder ein 0,1-Kante ist)
Habe ich doch gesagt - das hängt von der Spalte ab, die du betrachtest (0 0 1 steht für eine 0-Eigenschleife bei Zustand 0 und eine 1-Kante von 0 nach 1)
Deinen Versuch habe ich nur überflogen, aber er sieht richtig aus.
vip@r schrieb:
Ich hab dann hier auch gleich nochmal eine ähnliche Aufgabe. Mir ist die Sprache L gegeben mit der ich einen DEA entwerfen soll:
L = {w in ∑*Bool | w endet auf 01} Gibt's da jetzt auch wieder ein Schema? Oder muss man den DEA durch Überlegungen zusammenbauen?
Hier dann auch gleich mein Vorschlag: http://imageshack.us/photo/my-images/192/25505560.jpg/ Ist das so richtig?
Ja, das sieht so richtig aus, hat nur einen kleinen Schönheitsfehler: Das ist kein deterministischer Automat.
-
Das ist kein deterministischer Automat.
Hm, das ist natürlich dumm. Ich soll ja einen DEA basteln. Was fehlt da dann? An den fehlenden Zustandsbezeichnungen kann's ja eher nicht liegen, oder?
-
Es fehlt nichts an dem Automaten - da sind im Gegenteil Kanten zu viel (eine der beiden 0-Kanten vom Startzustand). Aber wie man aus einem NEA einen DEA bildet, hast du afair auch schon behandelt.
-
da sind im Gegenteil Kanten zu viel (eine der beiden 0-Kanten vom Startzustand)
Dann gehe ich mal davon aus, dass die 0 der Schleife zu viel ist. Ich denke aber nicht, dass du nun DEA zu einen NEA von Hand gewandelt hast. Bist du vielleicht deswegen so schnell drauf gekommen weil eine 0,1-Schleife am Startzustand eines NEA immer steht und beim DEA nicht? Oder ist das Schwachsinn?
-
Nein, ich bin darauf gekommen, weil von deinem Startzustand zwei 0-Kanten vorkommen - sowas ist bei einem NEA erlaubt, aber nicht bei einem DEA. Aber nachdem du schon einen NEA hast, kannst du den auch weiterverarbeiten (Stichwort: Potenzmengen-Konstruktion).
-
Ich hab's dann mal so versucht: http://imageshack.us/photo/my-images/714/47478780.jpg/
Richtig?
-
Erstens sind die Bezeichnungen davor genau verkehrt herum und zweitens scheint der DEA auch nicht ganz richtig zu sein - dort fehlen imho eine ganze Menge an Kanten.
-
sorry, aber ich wüsste nicht wo ich da noch mehr kanten haben soll...
