FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI 1- Probeklausur 2011 Aufgabe 10 / 11

FGI 1- Probeklausur 2011 Aufgabe 10 / 11 2011-07-24 14:28
Anonymer User
Hallo Leute, ich weiß es ist nichtmehr viel Zeit bis zur Klausur von 2011 und normalerweise würde ich auch nichtmehr Posten, aber das Problem das ich bei Aufgabe 10 / 11 Hab interessiert mich jetzt so brennend ich MUSS wissen warum ich das nicht verstehe.

Hier nochmal der Link zu den Aufgaben

Aufgabe 10 geht ja um rationale Ausdrücke , wobei a) und b) kein Problem sind.
Mein erstes Problem habe ich bei der Auswertung der eigentlichen Eigenschaft die die Sprache c jetzt haben soll. Höchstens ein Paar direkt aufeinanderfolgenden 1en würde ja entweder heißen: nicht mehr als 2 einsen ( also 111 wäre hier falsch, könnte man ja als 2 Paare sehen? evtl? vl tue das nur ich :D ) ODER nicht mehr als ein PAAR einsen, d.h. 111 wäre noch richtig, 1111 aber nichtmehr.
Ich habe versucht mir erstmal klar zu machen was ich für die Sprache alles brauche, d.h. 0 / 1 alleine sollen ja drinn sein, zweier paare etc, aber ich finde irgendwie keine Möglichkeit diese Beschränkung zu verwirklichen. Mein Ergebnis waren ellenlange kombinationen von 0* 01* 10* etc, wo ich mir einfach sicher bin das es viel zu kompliziert ist und irgendwo eine Lücke sein muss.

Was Aufgabe 11 angeht so wäre der vDFA zu a) und b ) wieder kein Problem, sind ja recht simpel. Bei C stehe ich aber wieder vor dem Problem dass ich nicht weiß wie ich die Beschränkung realisiere.
Ich habe erst einen Automaten mit Zwei Zuständen gemacht, Endzustand = Startzustand,
Bei 0 bleibt er im Startzustand und bei 1 geht er in einen Zweiten Zustand der bei 0 und 1 wieder zum Startzustand geht.
So konnte ich zwar realisieren dass Z.B. 11 noch akzeptiert wird, 111 aber nicht, offensichtlich werden aber zuviele Zustände nicht akzeptiert die ja eigentlich Teil der in 10 erzeugten Sprache sein sollen ( d.h. einfach nur 1, 01 etc )
Mit einer Falle oder mehr Zuständen habe ich dann wieder das ähnliche Dilemma - ich kriege entweder die Eingabe mit nur 1 Zeichen nicht akzeptiert oder Eingaben die falsch sein sollen nicht in einen Zustand der nicht der Endzustand sein soll.

Wenn ihr ein paar Ideen habt was ich übersehe wäre ich echt dankbar :)
Lg, Axel

RE: FGI 1- Probeklausur 2011 Aufgabe 10 / 11 2011-07-24 16:27
malexmave
Ich habe das mit dem paar Einsen so verstanden:
Erlaubt:
011010101010
Nicht erlaubt:
011011010100
011101010101

Also:
Zwei einsen nacheinander sind genau einmal erlaubt, danach nur noch einzelne einsen und beliebig viele nullen.

RE: FGI 1- Probeklausur 2011 Aufgabe 10 / 11 2011-07-25 00:16
theorinix
nicht mehr als ein PAAR einsen, d.h. 111 wäre noch richtig, 1111 aber nichtmehr.

111 hat doch zwei Paare von 11: die ersten zwei Einsen und auch noch die letzten zwei Einsen! Also wäre 111 doch auch jetzt nicht erlaubt.
Wo soll denn der Unterschied zwischen "höchstens ein Paar" und  "nicht mehr als ein Paar" sein? Für mich meint beides das das Selbe/Gleiche.

Nicht Vergessen, das leere Wort hat auch nicht mehr als zwei aufeinander folgende Ziffern 1!