Info08.de - Forum des Erstsemester Jahrgangs 2008

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

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

fredpape hat geschrieben: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...
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

Patric hat geschrieben:

fredpape hat geschrieben: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 hat geschrieben: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.

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

Christian S. hat geschrieben: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?

Patric hat geschrieben:

Christian S. hat geschrieben: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.

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

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