3. Automaten-Konstruktion

Automaten-Konstruktion

  • V

    Hi Leute!

    Ich will einen Automaten für die Sprache:

    L1 = {w Σ*Bool | w = 0v, v enthält gerade Anzahl Einsen}

    Ich sitz da jetzt schon einige Zeit drüber, komm aber nicht so wirklich auf die richtig Lösung. Meine bisheriger Automat sieht so aus:

    q0 -> 1 -> q0
    q0 -> 0 -> q1
    q1 -> 0 -> q1
    q1 -> 1 -> q2
    q2 -> 0 -> q2
    q2 -> 1 -> q3
    q3 -> 0,1 -> q1

    q0 ist Startzustand und q1 ist akzept. Zustand.

    Der Automat von mir oben erkennt, zwei Einsen im Wort w. Das ist aber nicht ganz die Frage...

    Könnt ihr mir helfen?

    0
  • C

    Wir hatten doch aair schonmal einen Automaten, um gerade Wortlängen zu erkennen. Darauf kannst du doch aufbauen.

    0
  • C

    vip@r schrieb:

    Ich will einen Automaten für die Sprache:

    L1 = {w Σ*Bool | w = 0v, v enthält gerade Anzahl Einsen}

    Meine bisheriger Automat sieht so aus:
    q0 -> 1 -> q0

    Wofür soll das gut sein? Wenn im Startzustand eine 1 kommt, bleibt er im Startzustand? Ich dachte du möchtest nur Wörter erkennen, die mit 0 losgehen? 😕

    Ich würde mit System an diese Aufgabe drangehen. Durch scharfes hinsehen erkennt man doch sofort, dass alles außer einer 0 im Startzustand zu einem dead-end führen muss. Danach "eine gerade Anzahl". Das hattest du doch letztens erst? Zwei Zustände, zwischen denen immer hin und her gesprungen wird.

    Ich muss sagen, deine Postings zu Automaten sehen für mich mehr und mehr danach aus, als möchtest du dir gar keine Mühe geben, sondern nur deine Hausaufgaben gelöst bekommen.

    0
  • V

    Ja, gerade Wortlänge. Aber was hat denn gerade Wortlänge mit gerader Anzahl an Einsen zu tun? Was gibts da für parallelen?

    0
  • C

    vip@r schrieb:

    Ja, gerade Wortlänge. Aber was hat denn gerade Wortlänge mit gerader Anzahl an Einsen zu tun? Was gibts da für parallelen?

    Sie sind beide gerade 😃

    0
  • V

    Ich muss sagen, deine Postings zu Automaten sehen für mich mehr und mehr danach aus, als möchtest du dir gar keine Mühe geben, sondern nur deine Hausaufgaben gelöst bekommen.

    Sorry, aber könnt ihr auch was anderes als auf Studenten rumzuhacken denen Theoretische Informatik einfach nicht so einfach fällt? Ich möchte mit Sicherheit die Aufgaben nicht einfach gelöst bekommen sondern den SCHEIß selber verstehen! Bloß was will ich machen, wenn ich nach 45 min. Überlegen und rumprobieren immer noch genau da stehe wo ich am Anfang war und auch keine Komillitonen in Aussicht sind, die ich "nerven" könnte!

    Komischerweise kommen solch dummen Kommentare über mich, auch immer nur von einer einzigen Person, Christoph!

    Ich sehe oft eben nur dieses Board als LETZTE Anlaufstelle wenn ich wirklich nicht mehr weiter weiß!

    Ich hoff, das war ENDLICH mal deutlich genug!

    0
  • V

    Ok, wenn sie sind beide gerade.

    Wenn ich mir nun aber so den Automat für gerade Wortlänge ansehe, dann kann ich den zumindestens schon mal sowei umbauen, dass das so aussieht:

    Ich gehe jetzt nur vom Automaten für gerade Wortlänge aus, der ja nur 2 Zustände hat:

    q0 -> 0 -> q0
    q0 -> 1 -> q1
    q1 -> 0 -> q1
    q1 -> 1 -> q0

    q0 ist Start- und akzept. Zustand.

    Hier aber hab ich dann das gleiche Problem wie oben, dass nach zwei gelesen Einsen schluss ist, das Wort ja aber theoretische noch weitere Einsen haben könnte!

    0
  • C

    vip@r schrieb:

    Sorry, aber könnt ihr auch was anderes als auf Studenten rumzuhacken denen Theoretische Informatik einfach nicht so einfach fällt? Ich möchte mit Sicherheit die Aufgaben nicht einfach gelöst bekommen sondern den SCHEIß selber verstehen! Bloß was will ich machen, wenn ich nach 45 min. Überlegen und rumprobieren immer noch genau da stehe wo ich am Anfang war und auch keine Komillitonen in Aussicht sind, die ich "nerven" könnte!

    Was machen denn deine Komolitonen in der Zwischenzeit? Sitzen die genauso ratlos vor den Aufgaben - oder warten sie darauf, daß du ihnen die Aufgaben-Lösungen lieferst?

    Edit:

    Hier aber hab ich dann das gleiche Problem wie oben, dass nach zwei gelesen Einsen schluss ist, das Wort ja aber theoretische noch weitere Einsen haben könnte!

    Nein, danach ist nicht Schluß - du stehst wieder im Ausgangszustand und kannst von dort aus weitere Eingaben verarbeiten.

    Ansonsten mußt du jetzt nur noch sicherstellen, daß das Wort mit 0 anfängt 😉

    0
  • V

    Meine anderen Komillitonen sitzen genauso wie ich daheim und werden wahrscheinlich das gleiche tun wie ich... bzw. sitzen oft genauso ratlos vor den Aufgaben!

    0
  • J

    vip@r schrieb:

    Hier aber hab ich dann das gleiche Problem wie oben, dass nach zwei gelesen Einsen schluss ist, das Wort ja aber theoretische noch weitere Einsen haben könnte!

    Wo ist das Problem? Der Automat hält ja nicht an, nur weil er gerade in einem akzeptierenden Zustand ist. Den Teil behandelt er sogar schon richtig. Allerdings erzwingst Du noch keine 0 am Anfang.

    0
  • V

    Der Automat hält ja nicht an, nur weil er gerade in einem akzeptierenden Zustand ist.

    Danke für deine hilfreiche Antwort Jester! Du hast natürlich recht, dass der Automat nicht anhält, wenn er in einem akzept. Zustand ist. Der Automat hält natürlich erst an, wenn das Wort komplett gelesen wurde. Ich hab hier mal ein Bild von dem ich denke, dass es passen könnte: http://imageshack.us/photo/my-images/695/12791076.jpg/

    0
  • V

    vip@r schrieb:

    Bild von dem ich denke, dass es passen könnte: http://imageshack.us/photo/my-images/695/12791076.jpg/

    Richtig.

    0
Anmelden zum Antworten