Zusätzliche Übungsaufgaben - Blatt 2

[Kubik-Rubik]

http://gbi.ira.uka.de/uebung/blatt-uebung2-aufgaben.pdf

Lösungen bitte hier posten!

Edit: Lösungen online - http://gbi.ira.uka.de/uebung/blatt-uebu ... sungen.pdf

[fredpape]

Bei der Aufgabe Ü.15 a) gibt es meiner Meinung nach unendlich viele Klassen, oder hab ich was übersehen?

[Patric]

Bei der Aufgabe Ü.15 a) gibt es meiner Meinung nach unendlich viele Klassen, oder hab ich was übersehen?

Jo, soweit ich weiß hat jede Typ 2 Sprache (kontextfreie Grammatik) unendliche viele Klassen. Und da sich da um eine Typ 2 Sprache handelt

[Thomas]

weiß auch net was die aufgabe soll...
genau wie bei der 16 b) und c) das is doch offensichtlich dass das stimmt wenn f(n) = f(0) für alle n € N0 dann is doch auch f(kn) = f(0) k € N

[fredpape]

Bei der Aufgabe Ü.15 a) gibt es meiner Meinung nach unendlich viele Klassen, oder hab ich was übersehen?

Jo, soweit ich weiß hat jede Typ 2 Sprache (kontextfreie Grammatik) unendliche viele Klassen. Und da sich da um eine Typ 2 Sprache handelt

weiß auch net was die aufgabe soll...

Gut, es freut mich zu hören, dass ich da nicht der einzige bin dem das komisch vorkommt.

[Christian S.]

Die Automatenaufgabe mit dem Ersetzen kommt mir auch komisch vor, schließlich "weiß" ja ein endlicher Automat nicht wann keine Zeichen mehr eingegeben werden.

[Patric]

Die Automatenaufgabe mit dem Ersetzen kommt mir auch komisch vor, schließlich "weiß" ja ein endlicher Automat nicht wann keine Zeichen mehr eingegeben werden.

Wenn er ein leeres Feld liest?

[Christian S.]

Die Automatenaufgabe mit dem Ersetzen kommt mir auch komisch vor, schließlich "weiß" ja ein endlicher Automat nicht wann keine Zeichen mehr eingegeben werden.

Wenn er ein leeres Feld liest?

Ein Mealy-Automat kann kein leeres Feld lesen, da er nicht selbständig arbeitet sondern mit Zeichen "gefüttert" wird. Und g*(z, €) = € per Definition, also kommt das leere Wort auch nicht in Frage.

[Kubik-Rubik]

Mittlerweile wurden Lösungen zu diesen Übungsaufgaben veröffentlicht -> http://gbi.ira.uka.de/uebung/blatt-uebu ... sungen.pdf

[Romeo]

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

Ich bin im Moment etwas ratlos.

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