Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Automatenquiz
Wie war das noch - den Univ. Informatiker unterscheidet sein theoretisches Fachwissen vom FH-Informatiker?
Das kleine Quiz hier stammt von der FH Nürnberg und ist vielleicht ganz nett zum Üben: http://www.informatik.fh-nuernberg.de/Professors/Schiedermeier/SS_2002/IVS/Courses/index.htm (geht teilweise nur mit IE)
hast du den stoyan damals wirklich ernst genommen?
Nein, ich fands nur ziemlich arrogant.
So im groben und ganzen glaub ich schon, dass die univ. Ausbildung mehr auf Grundlagen baut, wobei man auch zugeben muss, dass bei uns diese nicht sehr erfolgreich gelegt werden. So ein Onlinequiz ist gleich viel ansprechender als Uebungsblaetter oder Probeklausuren.
Auch wenns euch wahrscheinlich schwer faellt: macht mal was falsch, die Antworten darauf sind net schlecht.
hey das teil ist klasse.
gibts noch mehr solcher sachen?
so macht ThI - lernen Spass 
Cool, das Ding macht ja voll Spaß…
Frage 8:
Ich hab 2 und 3 angekreuzt (3 folgt aus 2), aber das Ding meint: “Aussage 2. ist unwahr. Nicht alle erreichbaren Zustände müssen Endezustände sein.” Wieso das? Wenn ein Wort zur Sprache gehört, dann komm ich auch nen Endzustand. Und der Automat soll doch genau die sprache erkennen, oder wie?
Noch verwirrender ist für mich die angeblich korrekte Antwort 4: Wie sieht denn die Schnittmenge aus einer Zustandsübergangsfunktion und eine Zustandsmenge aus?
Frage 9:
Wie sieht denn bitte dieser Automat aus? Mein NFA hat 9 Zustände und das scheint nicht klein genug zu sein. Für eine Sprache, die alles 4-stellige akzeptiert, außer “0000”, brauch ich aber 9 Zustände, oder? Ein DFA wäre noch länger, keine Ahnung, wie das jetzt gehen würde.
[quote=Yves]
Frage 8:
Ich hab 2 und 3 angekreuzt (3 folgt aus 2), aber das Ding meint: “Aussage 2. ist unwahr. Nicht alle erreichbaren Zustände müssen Endezustände sein.” Wieso das? Wenn ein Wort zur Sprache gehört, dann komm ich auch nen Endzustand. Und der Automat soll doch genau die sprache erkennen, oder wie?[/quote]
Ja aber ich komm ja bei nem NFA in mehreren Durchläufen in unterschiedliche Zustände, das können Endzustände sein oder halt “normale” Zustände aus denen ich nicht mehr rauskomm … und in einem dieser Durchläufe muss ich halt in einen Endzustand kommen, dann wird das Wort akzeptiert.
ne das is der Schnitt der erreichbaren Zustände mit den Endzuständen, das is semantisch äquivalent zur Aussage 3
zu 9:
also meiner ist deterministisch und hat 8 Zustände
a) om Startzustand aus habe ich zwei Möglichkeiten - lese ich als erstes eine Zahl >0 dann sind mir die restlichen Ziffern egal - muss also für jede Ziffer testen, ob 0-9 dabei ist. Macht Startzustand + 4 Zustände.
b) Lese ich aber als erste Ziffer eine Null, dann teste ich, ob die zweite und dritte Ziffer eine 0 ist. Dann darf als vierte Ziffer nur noch eine 1-9 kommen. Wenn bei der zweiten und dritten Ziffer was anderes als 0 kam, dann gehe ich in den entsprechenden Zustand von a).
Für den 000[1-9] brauch ich drei Zustände. (1-9) führt auf den Endzustand von a)
Macht also Startzustand + 4 +3 = 8 Zustände
Frage 12:
Wie finde ich das Wort der Differenzsprache raus? Meiner Erkenntnis nach akzeptiert A1 die Sprachen: bab | baa und A2 akzeptiert: ba | bab | babb | baaa*. Jedes Wort von A2 wird also auch von A1 erkannt.
Hast du ein Bild oder ne Tabelle davon? Ich kann dir nicht folgen.
tip: schwedische Pop Band
Schau dir die Unterschiede von beiden Automaten an.
In A1 kommt man von q1 und q3 mit einem b immer nur wieder nach q1 und q3.
In A2 kommt man aber von q1,q3 mit b nach q2,q3
Argh, ja, ich hab für A2 noch babba vergessen… irgendwie übersehen…
Zustand Übergangsfkt
z0 (z1, 1-9)
z1 (z2, 0-9)
z2 (z3, 0-9)
z3 (z4, 0-9)
z4 Endzustand
z0 (z5, 0)
z5 (z6, 0)
z5 (z2, 1-9)
z6 (z7, 0)
z6 (z3, 1-9)
z7 (z4, 1-9)
Ich hoffe, ich habe das jetzt keinen Fehler reingebaut. Als Automat sieht es relativ einfach aus.
EDIT: Ich glaub, eigentlich schreibt man das eher andersrum also Ziel = Übergangsfunktion - für die erste Zeile also (z0, 1-9 ) = z1
Bei Eingabe von 1-9 gehe von Zustand z0 in z1 über.
OK, danke für den Automat.
Neue Frage bei Aufgabe 20:
Wie soll da die Antwort lauten? Ne leere Eingabe scheint nicht richtig zu sein, ich denke aber, dass es das ist. Oder was bedeutet dieser * bei L? War das nicht die Potenzmenge, oder bestenfalls noch die bel. Wiederholung? In beiden Fällen kommt doch auch das leere Wort raus, was wohl zweifelsohne die kürzeste Lösung wäre.
Gib mal “l” ein - ein Epsilon oder Lambda is halt schwierig über so eine textbox. Das leere Wort ist aber korrekt.
Hm, hatte ein “e” versucht.
Neue Frage: Aufgabe 22, was bitte ist das Komplement einer Sprache? Oder eines Automaten?