Aufgabe 11.2

[Dre]

Wie sieht bei euch der endliche Akzeptor für c) aus? Der macht mich noch wahnsinnig.

[SLS]

Hmm, hast du den Akzeptor bei (a) ? Bei mir ist (c) sehr ähnlich (hat zum Beispiel diegleiche Anzahl von Zuständen). Wenn du die (a) richtig hast, sollst du auch schon die (c) lösen können.

Edit: Hab was Falsches gemacht, obiges gilt nicht! Entschuldigt

[Dre]

Also: a) is bei mir:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

--> 0 --a--> 1 --b--> 2 (/w a-Schlinge) <--b--> 4 --a--> A

Hilft mir wenig oder gar nicht. Bei c) fehlt entweder "aba" oder (ab^x)ba (außer "abba")

[SLS]

Dein a) sieht richtig aus (gegebenfalls du hast ja absichtlich hier den zusätzlichen Zustand, zu dem alle andere Eingaben führen (wo solche in der obigen Darstellung fehlen), nicht angegeben).

Edit:
Entschuldige, dass ich dich irregeführt habe, es ist gar nicht dasselbe wie in (a). Ich habe wahrscheinlich denselben Fehler gemacht wie du. Nun glaube ich schon, das ich es richtig habe.
Hier mein neues Ergebnis <Manchmal dummformulierte intuitive Beschreibungen, wie etwa "im Stern" im Sinne von "in dem ersten Teil des regulären Ausdrucks">:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Code: Alles auswählen

1. Da 'ba' akzeptierten werden muss, bekommen wir folgendes:

--> [-] --b--> [b] --a--> [[ ba ]]

2. Man sieht leicht ein, dass 'bb' nicht mehr akzeptierbar ist, dasselbe gilt für ba<irgendwas>

--> [-] --b--> [b] --a--> [[ ba ]]
                |            /
                |b          /
                v          / a,b
              [XXX]<------/
                U
               a,b

3. Nun ist das einzige, was nicht spezifiziert ist, [-] --a--> ? Es ist klar, das keiner der jetztigen Zustände dafür geeignet ist, also machen wir einen neuen:

    [a]
     ^
     |a
     |
--> [-] --b--> [b] --a--> [[ ba ]]
                |            /
                |b          /
                v          / a,b
              [XXX]<------/
                U
               a,b

4. Was ist wenn in [a] ein 'b' kommt? Es ist doch nicht [b], weil, so haetten wir nicht mehr die möglichkeit weitere 'a'-s und 'ab'-s zu schreiben (wir kommen "aus dem Stern heraus"), also machen wir einen neuen Zustand.

    [a] --b--> [ab]
     ^
     |a
     |
--> [-] --b--> [b] --a--> [[ ba ]]
                |            /
                |b          /
                v          / a,b
              [XXX]<------/
                U
               a,b

5. Wenn in [ab] nun noch ein b kommt, dann sind wir doch genau in [b] richtig, denn kommen zwei b's direkt nacheinander vor, so muss dann gleich ein a kommen und nichts mehr, damit das Wort akzeptiert werden kann.

    [a] --b--> [ab]
     ^          |
     |a         |b
     |          v
--> [-] --b--> [b] --a--> [[ ba ]]
                |            /
                |b          /
                v          / a,b
              [XXX]<------/
                U
               a,b

6. Wenn man nun in [ab] 'a' eingibt sollte es doch akzeptiert werden ('aba' ist akzeptabel), aber falls wir zum schon existierenden akzeptierenden Zustand [[ba]] gehen, können wir nicht mehr weiter im Stern bleiben, also brauchen wir einen neuen:

              [[aba]]
                  ^
                  |a
                  |
    [a] --b--> [ab]
     ^          |
     |a         |b
     |          v
--> [-] --b--> [b] --a--> [[ ba ]]
                |            /
                |b          /
                v          / a,b
              [XXX]<------/
                U
               a,b

7. Nun merkt man, dass bei [a] der Zustandsübergang durch Eingabe von 'a' fehlt. Aber es ist klar, dass mehrere 'a' nacheinander keine besondere Rolle spielen solange wir "im Stern sind", also wir machen dort eine a-Schlinge:

              [[aba]]
                  ^
                  |a
                  |
  ac[a] --b--> [ab]
     ^          |
     |a         |b
     |          v
--> [-] --b--> [b] --a--> [[ ba ]]
                |            /
                |b          /
                v          / a,b
              [XXX]<------/
                U
               a,b

8. Zurück zu [[aba]]: Was ist, wenn man hier 'a' eingibt? (abaa) ist nicht mehr akzeptiert, befindet sich aber im Stern, also man sollte mehrere a's eingeben dürfen und etwa (abaa.aaaa) rausbekommen. Dieses (abaa.aaaa) sollte man durch 'ba' zu einem akzeptierten Wort ergänzen können, oder auch einfach mehrere 'a's und 'ab's dazu hinzufügen. Hier kann ich es nicht so klar formulieren, aber es folgt für [[aba]]--a--> ? :

       ___a___[[aba]]
      /           ^
     |            |a
     V            |
  ac[a] --b--> [ab]
     ^          |
     |a         |b
     |          v
--> [-] --b--> [b] --a--> [[ ba ]]
                |            /
                |b          /
                v          / a,b
              [XXX]<------/
                U
               a,b


9. In [[aba]], Eingabe 'b': abab ist eigentlich immer noch "im Stern", hat aber das Potenzial durch ein 'a' zu einen akzeptierten Wort ergänzt zu werden (ababa). Irgendwie erscheint [ab] genau der richtige Platz dafür, denn somit könnte man von [ab] das Wort mit mehreren 'a'-s oder 'ab'-s harmlos ergänzen (ohne das das Wort sein Potenzial verliert, irgendwann akzeptiert zu werden):

       ___a___[[aba]]
      /        |  ^
     |         |b |a
     V         v  |
  ac[a] --b--> [ab]
     ^          |
     |a         |b
     |          v
--> [-] --b--> [b] --a--> [[ ba ]]
                |            /
                |b          /
                v          / a,b
              [XXX]<------/
                U
               a,b

Man kann sich jetzt folgende Bedeutungen der Zustände merken:
[-] bedeutet leeres Eingabewort
bedeutet entweder "Das Eingabewort hat mit b angefangen", oder "Es sind irgendwo im Wort zwei b's direkt nacheinander gekommen"
[ba] bedeutet "Das Eingabewort war nur 'ba' ", oder "Das Wort war bisher korrekt und endet nun mit "bba" (es ist auch klar das in diesem Fall auch ein a vor dem bba stehen muss)
[XXX] ist unser Papierkorbzustand und bedeutet hier "es sind am Anfang des Wortes zwei b's direkt nacheinander vorgekommen" oder "es sind drei b's direkt nacheinander vorgekommen" oder "es ist 'bb' vorgekommen, aber danach nicht genau ein 'a'"
[a] "Das Wort ist mit 'a' angefangen (mit Sicherheit!), der letzte Eingabezeichen war auch ein 'a', und wir sind >im Stern< (dürfen etwa (a|ab)* noch hinzufügen), diese letzte 'a' war dabei entweder an sich einfach 'a', oder der Anfag der Zeichenfolge 'ab' "
[ab] "Gerade haben wir ein "ab" aus dem Stern geschrieben, nun dürfen wir weitere ab's oder a's schreiben, wobei auch die Möglichkeit besteht, nur ein 'a' weiterzuschreiben, um das Wort akzeptabel zu machen"
[[aba]] "Das Wort endet auf aba und es kommt bisher 'bb' nirgendwo vor" - "Es ist nicht klar, ob wir am Ende eines zu akzeptierendes Wortes sind, oder immer noch im Stern und weitere 'a's und 'ab's erwarten"
Nun kann man sich noch sinnvollere Namen ausdenken, wenn man die eigentliche Bedeutung erkennt hat

P.S. Übrigens, ich würde dir empfehlen, sinnvollere Namen für deine Zustände auszuwählen (die wirklich der Bedeutung des Zustands entsprechen), und nicht etwa 1,2,3,4, aber es ist natürlich auch schon so richtg

P.S. 2: Ich hatte es zunächst bis einschliesslich Schritt 5 genau so wie oben, habe aber danach einfach noch zwei Pfeilen (und keine neue Zustände) hinzugefügt und somit den Fall "aba" vergessen. Wenn man auch dasselbe gemacht hat, ist es naheliegend, dass man einen neuen Zustand braucht [[aba]], und danach überlegt man sich wie oben.

[Dre]

Erstmal, woooooah wie lang bist daran gesessen.

P.S. Übrigens, ich würde dir empfehlen, sinnvollere Namen für deine Zustände auszuwählen (die wirklich der Bedeutung des Zustands entsprechen), und nicht etwa 1,2,3,4, aber es ist natürlich auch schon so richtg

Eh ja, gut ich wollt mich hier jetzt nicht so derart verkünsteln, aber trotzdem verständlich sein.

Dein endlicher Akzepter nach Schritt 5 is bei mir auf meinen unzähligen (durchgestrichenen) auch mal aufgetaucht.
Aber meiner Meinung nach dürfen die Eingaben "ababa" nich in einem akzeptierten Zustand enden.

Trotzdem danke für den ausführlichen (und überaus anschaulichen) Post.

[SLS]

Aber meiner Meinung nach dürfen die Eingaben "ababa" nich in einem akzeptierten Zustand enden.

Wieso? Der reguläre Ausdruck in der Aufgabenstellung lautet: (a|ab)*ba
Und es gilt: ababa = ab.a.ba
Wobei "ab.a" zu dem "(a|ab)*" Teil passt, und der Rest "ba" ist der notwendige (d.h. sternlose) Postfix ba.

Vielleicht versucht du es als a.ba.ba zu betrachten, wobei die letzten zwei Zeichen anscheinend das Wort kaputtmachen. Es ist aber wegen obiger Überlegungen nicht so.

Ich glaube, das Verständnisproblem ist darauf zurückzuführen, dass die zwei Ausdrücke auf beiden Seiten von | nicht präfixfrei "zueinander sind" (etwa 'a' ist Präfix von 'ab'). Nun merkt man, wieso bei Huffman-Codes alles präfixfrei ist - damit die Interpretation immer eindeutig ist, ohne zu viel "nachdenken" zu müssen

[Dre]

Ach, ja klar... Ne war grad ne geistige Blockade bei mir, sry.

[jcdmb]

kann man überhaupt [ba] als Eingabe haben? Soweit ich weiss es soll entweder a oder b sein.
Wenn [ba] als Eingabe gilt finde ich die Lösung akzeptabel