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

0 Pluspunkte 0 Minuspunkte
61 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)  
...