Fachrat Informatik - Forum

Das kommt einfach aus zwei verschiedenen Teilgebieten: "Akzeptierbar" ist aus der Theorie der formalen Sprachen. "Semi-entscheidbar" aus der Berechenbarkeitstheorie. Und dann kann man am Ende sehen, dass sich die beiden Gebiete halt überschneiden.

Bei der Uhrzeit und dem Raum für die Klausur hat sich nichts geändert oder? Also um 13:30Uhr im Audimax?

MfG

Laut webseite 13:45 aber man muss ja nicht auf die letzte Sekunde kommen :-)

In der Klausur heute kam folgende Aussage bei Aufgabe 1 vor:
Es gibt Typ-i Sprachen, die nicht vom Typ-(i + 1) sind, für alle 0 <= i <= 2.

Die Aussage ist doch Richtig oder?

MfG FSW

Die Lösung der Klausur gibt es im StudIP.

Ja, das ist richtig.
Lösungshinweise zu den Klausuraufgaben finden sich jetzt übrigens in den Stud.IP-Veranstaltungen zur KvA-Übung und zur letzten GdThI-Übung.

@Ryoga: Man kann da eine LOOP-Schleife ums Potenzieren drumrum machen.

weil das ne schleife ist die bis n läuft. nix unendliches oder sonstwie komisches...
btw: danke für den hinweis mit lösung ims tudip

habe mich in der Zeile vertan, ging um 6. Wieso ist das Komplement von einer Typ-0 auch wieder Typ-0? das habe ich als falsch angekreuzt

ich hab den Automaten genau anders rum, 0 und 1en vertauscht und der Start und Endzustand natürlich auch, das ist dann wohl falsch, oder ?

stimmt das habe ich auch
wäre das kompliment vom typ 0 so wäre die sprache ja vom typ 1... wobei jede typ 1 sprache auch vom typ 0 ist... verdammt, das -4 punkte

Danke für den Hinweis.

also ist in der lösung aufgabe 1 frage 6 nicht falsch eingetragen? das wäre echt scheisse -.--

Quoted from "Ryoga`"

Wieso ist das Komplement von einer Typ-0 auch wieder Typ-0?

Die Multiplechoice-Aufgabe lautete: Es gibt eine Sprache L vom Typ 0, so dass auch ihr Komplement vom Typo 0 ist.
Das gilt z.B. für jede reguläre Sprache, die natürlich auch Typ 0 hat.

Uiha, das ist ja gut dass die Lösung schon da ist.

Ein paar Fragen/Anmerkungen:

Bei Aufgabe 1 werden nicht angekreuzte Antworten gar nicht gewertet, oder? Habe ganz vergessen, das vor der Klausur zu fragen. Habe nämlich vorsichtshalber bei den unsicheren Sachen nichts angekreuzt.

Zu A2, da habe ich einen etwas umständlicheren Automaten:



Müsste aber auch volle Punktzahl geben, oder? Zumindest habe ich keinen Fall gefunden, für den der Automat was falsches akzeptiert. Man könnte die Sprache doch einfach auch formulieren als "alle Wörter, die mit einer 1 enden", oder?

Hm, bei Aufgabe 3 habe ich den Anfang so wie im Lösungshinweis und habe dann argumentiert, dass vwx aus höchstens 2 verschiedenen Buchstaben bestehen kann (Beispielwort habe ich gewählt). Dann gibt es nach dem Aufpumpen auf mehr a's als d's, und das darf nicht sein. Ist das auch richtig?

Der Algorithmus zu Aufgabe 4 ist mir in der letzten Minute klar geworden, habe dann aber leider keine Zeit mehr gehabt, ihn vollständig aufs Papier zu bringen und habe das, was noch fehlte schnell in Stichpunkten weiterformuliert. Ich hoffe die Bewertung ist gnädig und gibt da ein paar Punkte drauf.

Woohoo, Aufgabe 5 habe ich ja sogar richtig! Auch wenn ich da sehr viel Text im Vergleich zur Musterlösung geschrieben habe (erst Mal gesagt, dass L berechenbar ist, da endlich, und dann gezeigt, dass der Satz von Rice daher für L gilt, da L Teilmenge aller berechenbaren Funktionen aufgrund der Endlichkeit und somit unentscheidbar nach dem Satz).

1) das immer so bei multiple choice ;-)
2) epsilon und 1 waren auch in der sprache
3) wenn du so b und c pumpst dann ist das wort noch in der sprache wenn ich das grad noch richtig im kopf hab. Das Problem hatte ich nämlich mit meinem ersten Beispielwort

Quoted from "AlexL"

2) epsilon und 1 waren auch in der sprache
3) wenn du so b und c pumpst dann ist das wort noch in der sprache wenn ich das grad noch richtig im kopf hab. Das Problem hatte ich nämlich mit meinem ersten Beispielwort

Ahh Mist, das hab ich übersehen. Ich hoffe das gibt trotzdem gnädige Teilpunkte :/ Ebenso beim Pumping Lemma.

dann hab ich den epsilon-fall bei dem automaten auch vergessen,
hoffentlich gibt es teilpunkte, im vergleich zu früher gab es für jede aufgabe ja viel mehr punkte

Quoted from "Skuld"

Zu A2, da habe ich einen etwas umständlicheren Automaten:
Müsste aber auch volle Punktzahl geben, oder? Zumindest habe ich keinen Fall gefunden, für den der Automat was falsches akzeptiert. Man könnte die Sprache doch einfach auch formulieren als "alle Wörter, die mit einer 1 enden", oder?

Das leere Wort gehört auch zur Sprache.

Hab auch ne Frage: wieso wurde bei der Lösung von 4 "x_2 := 0" benutzt? das doch gar nicht eine der erlaubten erweiterungen.