Automatenquiz


Hm, nochwas zur 27. Ich brauch eigentlich 3 Zustände, nur wenn ich ne unsichere Annahme mache, kann ich mit 2en auskommen. Die beiden sehen dann so aus:

z0, 0 → z0, “0”
z0, 1 → z1, “1”
z1, 0 → z1, “1”
z1, 1 → z0, “0”
start: z0

Der Startzustand selber darf aber keine Ausgabe machen. Wie ist das festgelegt, macht der sowas oder nicht? Wenn es es macht, brauche ich einen extra Startzustand, der keine Ausgabe macht.


22: Ein Wort welches A1 erkennt und A2 nicht: aa


Uh, die 28 ist ja schlimm!
— 1. Ein zusammenhängender Automat hat keine “unerreichbaren” Zustände.
Sag ich nein, sagt der doch. Wie soll denn das bitte gehen? Wenn ich nen Zustand mache, von dem aus nur ein Pfeil weggeht, aber keiner hin, dann ist der doch nicht erreichbar, aber trotzdem zusammenhängend.
— 2. Ein reduzierter Automat ist immer zusammenhängend.
Sag ich ja, sagt der nein. Da hab ich wohl was missverstanden. Was ist denn eigentlich ein “reduzierter Automat”? Ich hab sowas noch nie gehört. Ein minimierter Automat kann es wohl kaum mehr sein, nach den Antworten.


Ja, auf dem einfacheren Weg bin ich da schon auch drauf gekommen, aber die Ausgabe will ja, dass ich mit irgendwelchen Komplementen durch die Gegend rechne, nur weiß ich nicht, wie das geht.


Naja die Menge der Wörter, die A2 erkennt ist {a, b, ba, bb}
A1 erkennt {a, aa, b}. Die Negation von A2 wären also alle Wörter außer {a, b, ba, bb}. Also kann ich aus der Menge von A1 das “a” und das “b” streichen. Bleibt als Rest noch aa.


Und was ist dann die Negation der Sprache der Wörter {0, 1, 01, 110, 01100}?


27: würde ich jetzt eher ignorieren, da bei uns kein Moore / Mealy drankommt - das wäre mehr was zu OTRS gewesen. Aber Prinzipiell gebe ich dir recht.
Über 28 hab ich mich auch schon mit Komilitonen gestritten, da bin ich mit dir einer Meinung. Ich kenn aber auch die genaue Definition von “erreichbar” des Profs nicht. Bei reduziert und minimal ist das selbe Problem. Ich sehe da nicht wirklich einen Unterschied, aber vielleicht hatten die da was unterschieden.


Alle Wörter, die nicht {0, 1, 01, 110, 01100} sind. (Es sollte aber eine reguläre Sprache sein, sonst kann es sein, dass sie nicht über Komplement abgeschlossen sind. Nachdem es aber nur endlich viele Wörter in deiner Sprache gibt, ist sie sowieso regulär)


Ja, genau das war ja meine Frage. Zähl doch mal alle Wörter auf, die nicht in der o.g. Menge sind. Dazu müsste ich ja erstmal ne Menge aller “möglichen” Wörter haben. Blöderweise ist die unendlich groß, wenn ich mich nicht täusche.
Hm, Aufgabe nochmal angeschaut, OK. Das Komplement allein lässt dich wohl nicht berechnen, weil ich niemals damit fertig würde. Durch die Schnittmenge brauch ich dann aber wohl nur jedes Wort der linken Seite durchzugehen und kann prüfen, ob es nicht in der rechten Menge enthalten ist. Nagut. Is aber schon irgendwie kompliziert ausgedrückt…


Es heißt ja nur, dass so eine Sprache existiert. Daraus muss aber nicht zwangsläufig folgen, wenn die eine endlich ist, dass es auch die andere ist. Weiß nicht, ob man vielleicht da sogar ne Regel draus machen kann, wenn man das Komplement einer endlichen (abzählbaren) Sprache nimmt, dass das Ergebnis dann immer unendlich ist (aber durch einen endlichen Automaten erkannt werden kann, da regulär und ja über Komplement abgeschlossen). Da bin ich leider zu dumm, um sowas zu beweisen… :-p


Wie ist Aufgabe 33 zu lösen? Ich scheitere kläglich daran, das Ding zu minimieren. JEdenfalls geht es nicht minimal und irgendwie hab ich das Gefühl ist nach meinem Algorithmus alles minimal…


Aufgabe 45: Bin ich jetzt blind oder was? Die Grammatik wäre angeblich nicht rechtslinear, weil eine Produktion S → bBa existieren soll. Wo steht die? Ich seh die nicht.


aus S kann aA ODER bBa werden (1. Regel)


zum Inversen einer Sprache (in dem Fall regulär):
Hab gelesen, dass das am ‘einfachsten’ geht indem man einen Automaten zur Sprache L aufstellt und dann durch Inversion der Endzustände(also Endzustand → nicht Endzustad und umgekehrt) den Automaten der Sprache L[sup]-1[/sup] erhält, den man dann wieder in einen regulären Ausdruck packen kann.
Wodurch auch gleich bewiesen ist, dass reguläre Sprachen über Inversion abgeschlossen sind (wegen dem Automaten).


Also bei mir steht da:
S → aA | bBA
und das A ist in dem Fall großgeschrieben. Siehst du was anderes auf deinem Bildschirm?

Claudius: Dein Invers-Automat muss vorher aber vollständig gewesen sein, oder?


öhm - denk schon, sonst fehlen dir ja 'ne Menge Eingaben… (alle für den Fehlerzustand)


verdammt, er hats gemerkt… :rolleyes: