Seite 2 von 3
Re: Zusätzliche Übungsaufgaben - Blatt 2
Verfasst: Mi 4. Mär 2009, 14:39
von fredpape
Romeo hat geschrieben:Guten Morgen,
Zu 22:
Die Lösung, wie sie auf der GBI-Homepage veröffentlich wurde, erscheint mir persönlich nicht einsichtig.
Mein erster Ansatz hatte auch so ausgesehen, dieser hatte aber die Schwäche, die Christian sehr richtig angemerkt hat: Wenn ich beispielsweise nur ein "a" eingebe, so erhalte ich als Ausgabe
, was ja definitiv nicht dem gesuchten Wort entspricht (welches doch einfach w' = a sein müsste!?).
Noch schlimmer wird es beispielsweise bei der Eingabe von "ab"...
[...]
Habe ich auch gerade bemerkt, als ich die Aufgabe gemacht habe. Bin auf den gleichen Automat gekommen, wie er in der Lösung steht und dann ist mir eingefallen, dass er nicht stimmt (man gebe z.B. abba oder a ein) und es überhaupt gar nicht möglich ist so einen endlichen Mealy-Automaten zu konstruieren.
Was mir allerdings auffällt ist, dass der Automat in der Lösung bei Zustand 2 einen Doppelkreis hat, so wie bei einem Akzeptor (2 € akzeptierte Zuständsmenge F?). Was wollen die uns damit sagen? o.O
Re: Zusätzliche Übungsaufgaben - Blatt 2
Verfasst: Mi 4. Mär 2009, 15:22
von Romeo
Was mir allerdings auffällt ist, dass der Automat in der Lösung bei Zustand 2 einen Doppelkreis hat, so wie bei einem Akzeptor (2 € akzeptierte Zuständsmenge F?). Was wollen die uns damit sagen? o.O
Ja, das habe ich dann einfach ignoriert, weil ich mich so oder so schon so unwohl gefühlt habe
Hat jemand vielleicht noch eine Idee wegen der 20 a)?
Grüße
Roland
Re: Zusätzliche Übungsaufgaben - Blatt 2
Verfasst: Mi 4. Mär 2009, 16:01
von fredpape
Romeo hat geschrieben:[...]
Edit - Zu 20a:
Mir ist noch etwas aufgefallen - vielleicht bin ich auch zu unvermögend, um die Richtigkeit der Lösung zu erkennen:
Der Automat in der Lösung sieht ja sehr elegant aus, doch bekomme ich ein Problem mit der zweiten Hälfte des regulären Ausdrucks:
Angenommen, ich habe eine korrekte "linke Hälfte" eingegeben (bspw. "b"). Dann bin ich im akzeptierenden Zustand 2. Jetzt darf ich nur noch beliebig viele "rechte Hälften" konkatenieren (bspw. "bbbabba"). Was ich - meines Erachtens! - nicht machen darf ist, dass ich jetzt bspw. nur mit "bbb" konkateniere, da
in jeder rechten Hälfte genau
vorkommen muss.
Der vorgestellte Automat allerdings würde so etwas anstandslos akzeptieren...
Vielleicht ist das heute auch nicht mein Tag - man möge es mir i.d.F. nachsehen
Grüße
Roland
Ich sehe das genau so wie du, wenn man nach Eingabe einer korrekten linken Hälfte (Zustand ist dann also 2) noch ein oder mehrere einzelne b's eingibt, dann bleibt der Automat von der Lösung ja im akzeptierten Zustand 2, was aber falsch ist, da jeder rechte Teil genau 2 a's enthalten muss.
Ich kann mir nicht vorstellen, dass die Lösungen von Ü.20 a) und Ü.22 richtig sind.
Re: Zusätzliche Übungsaufgaben - Blatt 2
Verfasst: Mi 4. Mär 2009, 18:03
von riQ
Kann euch nur zustimmen hinsichtlich 20a) und 22. Imo ist die 22 nicht lösbar.
Für 20a) wäre mein vorschlag:
Re: Zusätzliche Übungsaufgaben - Blatt 2
Verfasst: Do 5. Mär 2009, 10:44
von Romeo
Guten Morgen,
Muss der linke, untere Zustandsübergang nicht ein b sein? Sonst wäre dein Automat nicht deterministisch.
Der Zustandsübergang unten soll doch wahrscheinlich mit "a" beschriftet sein oder?
Ansonsten habe ich diese Lösung auch!
Grüße
Roland
P.S. Ich glaube, man kann sogar einen Zustand sparen: Man kann den Zustand rechts oben als den von rechts unten verwenden. Man muss nur noch den Zustandsübergang "z+" --a--> "z_ro" hinzufügen und den Rest umhängen...
Re: Zusätzliche Übungsaufgaben - Blatt 2
Verfasst: Do 5. Mär 2009, 14:24
von riQ
Jo die beiden Sachen hab ich falsch übernommen/vergessen.
Nach deinem Vorschlag siehe Anhang sollte auch gehen.
Re: Zusätzliche Übungsaufgaben - Blatt 2
Verfasst: Do 5. Mär 2009, 15:04
von Kubik-Rubik
riQ hat geschrieben:Jo die beiden Sachen hab ich falsch übernommen/vergessen.
Nach deinem Vorschlag siehe Anhang sollte auch gehen.
So haben wir es auch...
Übung 20 a.)
Verfasst: Do 5. Mär 2009, 15:34
von Kubik-Rubik
Wir haben Herrn Worsch angeschrieben, er hat die Richtigkeit unserer Lösung bestätigt und die Lösung aktualisiert!
http://gbi.ira.uka.de/uebung/blatt-uebu ... sungen.pdf
Re: Zusätzliche Übungsaufgaben - Blatt 2
Verfasst: Do 5. Mär 2009, 15:41
von salami
Habe mal eine Frage zu 19 6).
Wäre b*(a*b*|a*) auch eine Lösung?
Re: Zusätzliche Übungsaufgaben - Blatt 2
Verfasst: Do 5. Mär 2009, 15:46
von Kubik-Rubik
salami hat geschrieben:Habe mal eine Frage zu 19 6).
Wäre b*(a*b*|a*) auch eine Lösung?
Nein, da fehlen noch ein Haufen Wörter wie zum Beispiel aabba (irgendwas, wo bba vorkommt)!