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
41 Aufrufe
Hallo,

kann es sein das bei der Minimierung des DEA man beim ausfüllen der Tabelle auf zwei unterschiedlich markierte Felder kommt. Also bspw. bei S3 und S5 kann ich ja s1 und s3 oder s3 und s4 vergleichen. Bei s1/s3 komme ich auf ein X1 markiertes Feld, bei s3/s4 auf ein X2 markiertes Feld.

Ich bin grade etwas verwirrt. Ich hab mich nun immer am kleineren Zustand orientiert und bin aufs richtige Ergebnis gekommen. Bloß frage ich mich, ob ich etwas falsch mach oder ob das wirklich passieren kann? Und wie ich damit umzugehen habe, da mir das noch nicht in den Tuts oder Übungsbüchern unterlaufen ist.

LG und Vielen Dank!
in 2011-H-01 von uuiya uuiya Lernwillige(r) (680 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
 
Beste Antwort

Hey uuiya,

natürlich kann das sein. Du hast ja sozusagen mehrere Iterationen, in denen du die Tabelle immer wieder komplett durchläufst und jedes offene Feld erneut überprüfst. Findest du beispielsweise in der dritten Iteration ein Zustandspaar, welches auf ein bereits markiertes Feld zeigt, so markierst du das Feld dieses Zustandspaares mit X3

Dabei spielt keine Rolle, ob das bereits markierte Feld mit X0, X1 oder X2 markiert ist - es geht nur darum, ob es markiert ist oder nicht. 

Achtung: Wenn du dich bspw. in der dritten Iteration und weiter unten in der Tabelle befindest und ein Zustandspaar findest, welches auf ein Feld zeigt das weiter oben bereits mit X3 markiert wurde (also in der selben "Iteration"), so wird dieses noch nicht mit betrachtet. Das würde man dann erst beim nächsten Durchlauf, also in der 4. Iteration, mit X4 markieren.

Beste Grüße,

Martin (Tutor)

von usifu usifu Eins-Komma-Null-Anwärter(in) (3.0k Punkte)  
ausgewählt von uuiya uuiya
0 0
Hey Martin,
super schonmal danke!!

Zu deinem Achtung:
Aber bspw. wenn ich in der Iteration 1 bin und in der vorletzten Zeile und ich treffe mit einem Variablenpaar auf ein x1 markiertes Feld, welches weiter oben steht. Aber mit dem anderen Variablenpaar auf ein x0 markiertes Feld was weiter unten steht. Wie gehe ich dann vor? Ich hab es dann als x1 markiert was auch richtig war. Aber warum?

Liebe Grüße und vielen Dank!
0 0
Hey,
das ist ein super Beispiel, warum es wichtig ist, immer beide Zustandspaare zu überprüfen. In deinem Fall ist die Markierung mit x1 richtig. Das erste betrachtete Paar (bspw. für Eingabe einer 0), welches auf ein weiter oben mit x1 markiertes Feld zeigt, betrachten wir quasi noch gar nicht. Stell dir vor, dass wir einen Durchlauf immer erst ganz am Ende "verbuchen", also bevor wir in den nächsten Durchlauf starten. Erst dann werden die Markierungen, in diesem Falle x1, für uns sichtbar und relevant. Das ist auch der Grund, warum du das Feld dann mit x1 markierst: Du befindest dich in Iteration 1 und dein zweites Zustandspaar zeigt auf ein Feld x0.
Soweit verständlich? :)
0 0
Hey,

ich denke schon, ja danke!! D.h. wenn ich in Interation 1 bin betrachte ich eigentlich nur die Felder welche mit x0 markiert wurden da die mit x1 markierten Felder eigentlich noch nicht sichtbar für mich sind, oder?

Und nochmal ganz kurz dass ich auch weiss das wir von der selben Interation 1 sprechen: Interation 1 = Erster Durchlauf nachdem wir die Felder mit X0 markiert haben?:D
0 0
Exakt so war es gemeint, sehr gut :) Entsprechend betrachtest du in Iteration n immer nur die Felder, die mit höchstens X(n-1) markiert sind. Also bspw. im dritten Durchlauf die Felder mit X0, X1 und X2.
Und richtig, das wäre die erste "Iteration". Das Wort dient hier aber nur dazu, es anschaulicher zu machen und ist keineswegs als formal korrekt zu betrachten. Aber ja, nachdem wir unsere X0 Felder markiert haben, starten wir sozusagen mit dem ersten Durchlauf / der 1. Iteration. :)
0 0
Top, vielen Dank für deine Zeit und die Geduld ;)
...