3. Automaten aus gegebener Sprache konstruieren

Automaten aus gegebener Sprache konstruieren

  • V

    Und wie berechnet man dann die Tabelle? Wenn du mir das sagen könntest wär ich glücklich 🙂

    0
  • C

    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".

    0
  • C

    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)

    0
  • V

    Ich komm jetzt auf:

    n%5 | n0%5 | n1%5
------------------
 0  |  0   |   1
 1  |  2   |   3
 2  |  4   |   0
 3  |  1   |   2
 4  |  3   |   4

    Stimmt's jetzt? Wenn ja, wie kann man nun daraus den DEA ablesen?

    0
  • C

    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.

    0
  • C

    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. 🙂

    0
  • V

    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/

    0
  • V

    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?

    0
  • C

    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.

    0
  • V

    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?

    0
  • C

    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.

    0
  • V

    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?

    0
  • C

    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).

    0
  • V

    Ich hab's dann mal so versucht: http://imageshack.us/photo/my-images/714/47478780.jpg/

    Richtig?

    0
  • C

    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.

    0
  • V

    sorry, aber ich wüsste nicht wo ich da noch mehr kanten haben soll...

    0
  • C

    Hast du denn noch deine Unterlagen zur Umwandlung von NEA nach DEA greifbar? Ich skizziere mal den Anfang:

    Startzustand: q0 -> {q0}
    Zustand {q0}: 0: {q0, q1}, 1: {q0}
    Zustand {q0, q1}: 0: {q0, q1}, 1: {q0, q2} //Nachfolger sind alle, die von einem der genannten Zustände erreichbar sind
    ...

    0
  • V

    So, noch ein Versuch. Jetzt sollte es aber stimmen...

    0
  • C

    Fehlt noch eine Eigenschleife - und einige Kantenbezeichnungen 😉

    0
  • V

    genau deswegen hab ich den link auch wieder raus

    0
Anmelden zum Antworten