Beantwortet: Saalübungen 1 (Folien) NOT FOUND

Wed, 14 Dec 2016 08:50:47 +0000

Ha! Danke für den Hinweis. Das lag daran, dass das Wort "Übung" ein "Ü" enthält, und das hat der Server in irgendein Kauderwelsch übersetzt. Die Datei war also da, aber der Link hat knapp daneben gezeigt...

Jetzt tut der Link und er lautet:

http://info2.aifb.kit.edu/secure/Saaluebungen/Saaluebung1-Folien.pdf

Beantwortet: Unbeantwortete nuKIT-Frage vom 5.12.2016

Mon, 05 Dec 2016 17:21:12 +0000

Würden wir nur einen Zustand nutzen, könnten wir nicht unterscheiden, ob bereits $c$'s oder $d$'s aufgetreten sind oder nicht. Wir könnten dann immer von vorne anfangen und würden neue $a$'s und $b$'s akzeptieren, obwohl diese nach Definition nur am Anfang stehen dürfen.

Beantwortet: Lösung der Saalübung

Tue, 12 Jan 2016 06:50:07 +0000

Wir haben wohl vergessen, die Lösungen hochzuladen. Jetzt sind sie unter dem von Marvin angegebenen Link verfügbar.

Viele Grüße

Lukas König

Beantwortet: Beantwortung der nuKIT-Fragen, für die wir keine Zeit mehr hatten

Mon, 14 Dec 2015 14:48:34 +0000

Antwort zu 1.

Dieser Ausdruck ist leider nicht ganz korrekt. Das sieht man bespw. daran, dass Wörter der Form $0122^\star$ nicht konstruiert werden können, obwohl der endliche Automat sie erkennt. Trotzdem kann es sein, dass unser Lösungsvorschlag nicht den kleinsten möglichen regulären Ausdruck darstellt. Die Minimierung eines regulären Ausdrucks ist PSPACE-vollständig - das ist also noch schwieriger als wenn ein Problem NP-vollständig ist. Beides ist faktisch nicht lösbar, und so können wir nicht garantieren, dass wir einen besonders kurzen Ausdruck gefunden haben. (Auch Sie müssen das in der Klausur nicht tun.) Der beste bekannte Algorithmus zur Minimierung eines regulären Ausdrucks probiert im Wesentlichen alle regulären Ausdrücke bis zu einer gewissen Länge durch; er beginnt also mit der leeren Menge und generiert nacheinander immer längere reguläre Ausdrücke, wobei für jeden getestet wird, ob er die gewünschte Sprache repräsentiert.

Antwort zu 2.

Die Antworten auf diese Fragen kann man folgendermaßen zusammenfassen: det. end. Aut. haben wir so definiert, dass alle Übergänge explizit angegeben sein müssen. Daher kann man die Übergänge in die leere Menge nicht einfach weglassen. Bei Kellerautomaten ist das etwas anders; um sehr große Übergangsdefinitionen zu vermeiden, muss hier nicht jeder Übergang explizit angegeben werden. Der KA lehnt also ein Wort automatisch ab, wenn für eine Konfiguration kein zustandsübergang definiert ist. Ebenso ist das bei Turingmaschinen. Bei deterministischen TM wird die entsprechende Tabellenzelle einfach leergelassen, bei nichtdeterministischen schreiben wir an dieser Stelle das Leere-Menge-Symbol. (Wenn Sie die Zelle leerlassen, ist das aber auch in Ordnung.)

Antwort zu 3.

Wir verstehen nicht ganz, was mit dieser Frage gemeint ist. Können Sie das bitte nochmal präzisieren?

Antwort zu 4.

Wenn ich es gerade richtig sehe, ist die $0$ bei $\mathbb{N}$ nicht dabei, dafür müssen wir also $\mathbb{N}_0$ schreiben. Allerdings werden wir in der Klausur in dieser Hinsicht sowohl kulant sein als auch sehr präzise angeben, wovon Sie ausgehen sollen. Machen Sie sich keine Sorgen!

Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in Allgemeines

Beantwortet: Saalübungen 1 (Folien) NOT FOUND

Beantwortet: Unbeantwortete nuKIT-Frage vom 5.12.2016

Beantwortet: Lösung der Saalübung

Beantwortet: Beantwortung der nuKIT-Fragen, für die wir keine Zeit mehr hatten