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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
118 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?
in Allgemeines von Dozent (10.1m Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

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!

 

von Dozent (10.1m Punkte)  
Bearbeitet von
...