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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 0 Minuspunkte
50 Aufrufe
Ich verstehe nicht warum bis auf s0 keine Einzelzustände (also: s1, s2 und s3) betrachtet werden. Dies war doch das normale Vorgehen des Algorithmus in den Aufgaben zuvor.

So komme ich auf 7 anstatt der 4 Zustände.
in HU-2-1 von  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo,

wenn wir einen nichtdeterministischen Automaten deterministisch machen wollen, beginnen wir immer mit unserem Startzustand, der in der Regel s0 ist.
Danach arbeiten wir aber nicht die anderen Zustände des NEA ab. In unserer Übergangstabelle steht, welche Zustandsmengen erreicht werden, wenn wir im Zustand s0 eine Eingabe von 0 bzw. 1 erhalten ({s0,s1} bzw. {s0}). Nun nehmen wir alle Zustandsmengen in die linke Seite der Tabelle auf, hier also nur {s0,s1}, da wir für s0 ja bereits im ersten Schritt die Zustandsübergänge bestimmt haben, und gehen analog zu s0 vor. Dies tun wir, damit für jede Zustandsmenge in unserer Tabelle (die jeweils einen Zustand in unserem DEA darstellt) für jede Eingabe der Folgezustand (hier noch eine Menge von Folgezuständen) definiert ist. Da jede so erhaltene Zustandsmenge zu genau einem Zustand unseres DEA wird, hat somit jeder Zustand für jede Eingabe genau einen Folgezustand (siehe Definition DEA).

 

Ich hoffe, ich konnte dir weiterhelfen.

Liebe Grüße

Laura (Tutor)
von uxedh Tutor(in) (100k Punkte)  
...