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 pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur 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 cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
113 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
...