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

1 Pluspunkt 1 Minuspunkt
134 Aufrufe

Hallo,

irgendwie komme ich bei der k-Äquivalenz immer durcheinander, deshalb möchte ich mal fragen, ob ich die Definition richtig verstanden habe:

Als Ausgangspunkt habe ich einen EA A mit den Zuständen S und den dazugehörigen reduzierten Automaten A' mit den Zuständen S'.
Ein beliebiger Zustand a aus S und ein beliebiger Zustand b aus S' heißen k-äquivalent, wenn ich von beiden Zuständen a,b durch die Eingabe eines Wortes w (\( |w| \leq k\) ) sowohl bei A als auch bei A' in einen Endzustand gelange?

Wenn A und A' mehrere Endzustände haben, muss man dann in beiden Automaten in den gleichen Endzustand gelangen, damit die Zustände k-äquivalent sind oder reicht es aus, dass man überhaupt in einen Endzustand gelangt (sprich in bin in A in einem anderen Endzustand als in A')

Habe gerade auf Folie 2-34 gesehen, dass man die Definition der k-Äquivalen auch auf zwei verschiedene Zustände von ein- und demselben Automaten anwendbar ist.
Auch hier ist meine Frage, ob man bei mehreren Endzuständen durch das Wort in den gleichen Endzustand gelangen muss oder ob es egal ist in welchen Endzustand man gelangt, damit die beiden Zustän k-äquivalent sind

Danke und Gruß

 

in HU-1-4 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

Hallo,

zunächst geht es eigentlich nur um einen Automaten. Der reduzierte Automat A' fasst dann lediglich die im Automaten A äquivalenten (also k = unendlich) Zustände zusammen.

Das Ganze funktioniert immer rekursiv. Das heißt, du startest bei k = 0. Hier geht es darum, dass zwei Zustände 0-äquivalent sind, wenn sie entweder beide Endzustände sind, oder wenn sie beide Nicht-Endzustände sind.

Alles weitere lässt sich hierauf zurückführen.

Bsp: Von Zustand 1 gelange ich durch Eingabe 0 auf Zustand 1a und durch Eingabe 1 auf Zustand 1b.

Von Zustand 2 gelange ich durch Eingabe 0 auf Zustand 2a und durch Eingabe 1 auf Zustand 2b.

Die Eingabe hat die Länge eins. Wenn jetzt sowohl 1a und 2a 0-äquivalent sind, als auch 1b und 2b (es muss aber nicht "über kreuz" funktionieren), dann sind Zustand 1 und 2 1-äquivalent (du konntest, ausgehend von Zustand 1 und 2 einen Schritt gehen, ohne die 0-äquivalenz zu verlieren).

In dieser Weise erweiterst du dein Wort. Wenn sich an der k-äquivalenz nichts mehr ändert, dann weißt du von allen, die auf der höchsten Stufe sind, dass sie eben auch äquivalent sind.

Also kommst du mit diesen Zuständen, unabhängig von der Eingabe, auf das gleiche Ergebnis - sie sind somit redundant und können ausgelassen werden.

Ich hoffe, ich konnte dir ein wenig weiterhelfen.

Viele Grüße

Philippe (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...