klausur16

Question

Hallo,

in de aufgabe 1 a war verlangt , einen nicht minimalen , aber vereinfachten automaten mit nur einem eingabealphabet anzugeben. Hat jemand eine Idee wie so etwas gehen kann?

Comments

Genauer gesagt: "...einen möglichst kleinen, aber nicht ganz minimalen (und natürlich vereinfachten, sonst ist es ja langweilig) endlichen Automaten mit einelementigem Eingabealphabet."

Wie fanden Sie denn die Aufgabe?

---

Die Aufgabe war ok. Der Rest der Klausur eher weniger vor allem 6, 9 und 10 waren sehr undankbar.

---

Ich fand die Aufgabe zwar im nachhinein mehr oder weniger kreativ, aber eher verwirrend, als dass ich damit mein Verständnis des Themas gut hätte ausdrücken können.

Answer 1

Ich hätte dies als Lösung vorgeschlagen (Nur Überführungsfunktion):

Comments

Habe ich genauso! Aber jetzt wo du`s sagst, hab natürlich die Automaten vergessen und nur die Überführungsfunktionen geschrieben :(

---

Genau so kann man das machen, perfekt! Ich weiß nicht, was Sie mit "die Automaten vergessen" meinen, aber wenn wir erkennen können, was gemeint ist, werden Sie die Punkte bekommen. Diese Aufgabe war gedacht, um grundlegendes Verständnis von endlichen Automaten abzuprüfen - nicht um formal spitzfindig zu werden :-)

---

Wie haben Sie denn den d)-Teil gelöst, wo es darum geht, einen EA um einen Zustand zu erweitern, ohne dass sich die Sprache ändert?

---

Wäre auch ein Automat mit 3 Zuständen(2 Endzustände) möglich ?

---

Habe vergessen zu schreiben bei a) A=((a),(so,s1),.....) und bei b) A`((a),(so,s1),.....)

---

War das der Aufgabenteil, der nach einem zu einem minimierten Automaten mit n Zuständen einen mit n+1 gefragt hat?

Ich habe verneint und den Widerspruch mit einer Sprache beschrieben, die nur das leere Wort enthält. In dem Fall würde der Automat mit einem Zustand s0, der gleichzeitig auch der Endzustand ist, nicht auf zwei Zustände erweitert werden können. Soweit zumindest meine Gedanken während der Klausur, viel Zeit blieb dafür leider nicht.

---

Die Definition $A=\ldots$ war explizit nicht gefordert, damit Sie genügend Zeit zum Nachdenken haben.

Drei Zustände sind zu viel, das entspricht nicht dem geforderten Automaten (was nicht heißt, dass Sie dafür gar keine Punkte bekommen).

---

Okay, sehr gut :)

---

Der (d)-Teil war zugegebenermaßen schwer! Die richtige Antwort war, dass es geht - aber auch da werden wir uns in jedem Einzelfall die Argumentation anschauen und sicher auch Teilpunkte für nicht ganz korrekte Antworten geben.

---

Ein Automat der das leere Wort enthält hat doch beliebig viele Zustände, von denen nur einer Endzustand ist. In dem Fall kann man durch Einfügen eines Sackgassen-Zustands auch die n+1 Zustände erreichen...

---

Warum ist das mit dem leeren Wort nicht legitim? Ist der Automat dann ndet?

@uodvo: Dann wäre der Automat aber eben nicht vereinfacht.

---

vereinfacht heißt doch nur, dass alle Zustände erreichbar sein müssen. Mit Sackgassenzustand meine ich einen Zustand, den man zwar erreichen kann, aber der nicht wieder verlassen werden kann.

---

Ich lade Ihnen gleich die Aufgabe mit Lösungen hoch - wenn Sie schon so interessiert sind...

---

Es war ja auch nur nach der Überführungsfunktion gefragt. ;)

Answer 2

Das hier ist die Lösung der ganzen Aufgabe:

http://info2.aifb.kit.edu/qa/?qa=blob&qa_blobid=8058257473714026962

Comments

Wann wird die komplette Klausur hochgeladen?

---

Das müssen wir erst noch im Team besprechen. "Meine" Aufgabe habe ich in Eigenregie hochgeladen, aber die anderen müssen wir zuerst nochmal durchsehen. Jetzt gilt es aber erstmal, möglichst zügig mit der Korrektur durchzukommen.

---

Wie lang wird das ungefähr dauern?

---

Das kann ich so genau nicht sagen, denn es hängt nicht nur von uns ab. Ich hoffe, dass in spätestens zwei Wochen die Ergebnisse raus sind.

---

Ich möchte kurz vorweg nehmen, dass ich es super finde hier so schnell mit der Musterlösung konfrontiert zu werden - diesen offenen Umgang schätze ich sehr. Mir ist auch bewusst, dass es jetzt wenig Sinn macht über spezielle Lösungsansätze zu diskutieren. Dafür ist vielleicht die Klausureinsicht eher geeignet. Aber ein Punkt hätte ich (natürlich in eigenem Interesse) zu dieser Aufgabe vorzubringen:
Die letzte Frage gab ja 4 Punkte: Jetzt ist es so, dass ich (da ja Knobelaufgabe) etwas pragmatisch an die Aufgabe herangegangen bin und mich gefragt hatte: Was soll mit dieser Frage wohl abeprüft werden (also welches Verständnis). Da es in der Aufgabe um Minimierung ging war der Lösungsansatz recht schnell gefunden: Ein Minimierter Automat ist natürlich nie länger (also hat mehr Zustände) als der ursprüngliche. Wenn ich mir jetzt aber die Musterlösung anschau ziehlte die Frage mehr auf die "Allgemeinheit der EA's" ab (klar kann ich die beliebig kompliziert machen - aber dann sind sie ja nicht minimal). Muss ich dann wohl der traurigen Wahrheit ins Auge blicken und mit 0 Punkten rechnen oder  wie wollen Sie solche falschen Fälle in denen jedoch mächtig "Hirnschmalz" und auch richtiges Wissen und Verständnis für das Thema steckt. Ich möchte wirklich nichts schönreden oder irgendwie falschen.

---

Das müssen wir im Einzelfall sehen. Ich habe den Tutoren aufgetragen, bei dieser Aufgabe nach "kluger Argumentation" Ausschau zu halten und für diese Punkte zu vergeben, auch wenn die Grundaussage falsch ist (sogar, wenn Sie "nein" als Antwort geschrieben haben, kann es also noch Punkte geben). Wie viele genau hängt dann halt von der Klugheit des Geschriebenen ab :-)