Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

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

+1 Punkt
86 Aufrufe

Folgende Fragen konnten wir nicht (oder nicht vollständig) während der Saalübung behandeln:

  1. Zu Aufgabe 1: Geht das auch? 0*+((01)*+(02*)*)*
  2.  
    1. Warum lässt man die leere Menge nicht einfach weg und lässt die betroffenen Eingaben undefiniert?
    2. Lehnt der KA ein Wort automatisch ab, wenn für eine Konfiguration kein zustandsübergang definiert ist?
    3. muss man generell bei nichtdeterministischen Automaten/Turingmaschinen die leere Menge in der Tabelle benutzt während man bei deterministischen die entsprechenden Felder undefiniert
  3. Ist die Lösung bei A2, mit Angaben an den Übergängen mit 1x bzw Pfeil auf sich selbst, formal korrekt?
  4. Ist in Info2  N (natürliche Zahlen) so definiert, dass es 0 nicht enthält, sodass man dafür immer N0 schreibt?
Gefragt 14, Dez 2015 in Allgemeines von Lukas König Dozent (10,065,100 Punkte)  

Eine Antwort

0 Punkte

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!

 

Beantwortet 14, Dez 2015 von Lukas König Dozent (10,065,100 Punkte)  
Bearbeitet 14, Dez 2015 von Lukas König
...