View Full Version : [FRAGE] - Unterscheidbarkeitstabelle???
Hi Leute!
Kann viell von euch jemand kurz erlären, wie man auf die Unterscheidbarkeitstabelle kommt, spez. auf die Epsilon.
Viell geht auch an dem Konkreten Beispiel 4 von Übung 2.
Danke im voraus!
MFG Angel
Ja, das interessiert mich "leider" auch. :shinner: THX MfG HaPi
naja, an die Stelle (a,b) in der Unterscheidbarkeitstabelle kommt ein Epsilon <=> wenn a ein Endzustand ist und b nicht oder umgekehrt.
das sollte soweit klar sein, wenn du in einem Endzustand bist, heißt das, dein Automat hat das abgearbeitete Wort akzeptiert, wenn du in keinem Endzustand bist, dann ist es (noch) nicht akzeptiert -> deshalb sind solche Zustandspaare schon durch das Leerwort a.k.a. Epsilon unterscheidbar.
Danach "iterierst" du den Algorithmus aus dem Skriptum solange, bis sich nichts mehr in der Tabelle ändert -> die noch nicht markierten Paare in deiner Tabelle sind dann nicht unterscheidbar (es gibt kein wort, anhand dessen die beiden unterscheidbar wären).
und der Algorithmus selbst ist auch recht einsichtig: für jedes Symbol aus dem Eingabealphabet des Automaten schaust du, zu welchen Paaren du von den bisher noch nicht markierten Paaren hinkommst -> kommst du mit dem Symbol x zu einem Paar, das bereits als unterscheidbar durch das wort Y markiert ist, dann ist das momentan angeschaute Paar durch xY unterscheidbar (also schreibst du xY in die entsprechende Stelle der Tabelle). Was klar ist, denn mit x kommst du halt zu den beiden Zuständen, die schon durch Y unterscheidbar sind, und damit du von den momentan angeschauten Zuständen dorthin kommst, brauchst du halt das x...
und das wiederholst du jetzt einfach, bis du fertig bist....
Danke für die Erklärung, hab da aber noch zwei Fragen:
1) zwar wenn ich mir jetzt immer die Paare aus der Tabelle anschaue, und ich komm mit einem Wort zu zwei Endzuständen, ist das dann Epsilon?
z.B.
c...Endzustand; b...Normalerknoten
Schau mir jetzt an, wo ich hinkomme:
(b,c)--0--> (c,c) ... EZ,EZ ; folgt daraus jetzt ein Epsilon oder wie?
--1-->(d,d)
2) Was passiert, wenn ich von einem Zustand mit dem Wort nicht weiterkomme?
(b,d)--0-->(c,c)
--1-->(d,?) .... VOn d komm ich mit dem Wort 1 nirgends hin, was mach ich da?
MFG Angel
Mr.Anderson
30-06-2004, 12:43
Wie komm ich genau auf die Delta' Tabelle wenn ich die Unterscheidbarkeitstabelle fertig habe und ein paar Felder leer sind???
c...Endzustand; b...Normalerknoten
Schau mir jetzt an, wo ich hinkomme:
(b,c)--0--> (c,c) ... EZ,EZ ; folgt daraus jetzt ein Epsilon oder wie?
--1-->(d,d)
nein. 2 endzustände müssen nicht unterscheidbar sein. Epsilon kommt (wie bereits gesagt und erklärt) nur bei Paaren (EZ,NEZ) oder (NEZ, EZ)
2) Was passiert, wenn ich von einem Zustand mit dem Wort nicht weiterkomme?
(b,d)--0-->(c,c)
--1-->(d,?) .... VOn d komm ich mit dem Wort 1 nirgends hin, was mach ich da?
das kann/sollte nicht passieren, da deine Übergangsfunktion total sein sollte. Wenn sie nicht total ist, dann musst du eben noch eine Falle einbauen.
Wie komm ich genau auf die Delta' Tabelle wenn ich die Unterscheidbarkeitstabelle fertig habe und ein paar Felder leer sind???
wenn du 2 oder mehr zustände hast, die voneinander nicht unterscheidbar sind, dann entscheidest du dich für einen dieser Zustände, löscht die anderen und lässt alle Kanten/Übergänge, die auf einen der gelöschten Zustände gezeigt haben, auf den einen gewählten zeigen.
Note: 2 Zustände sind ununterscheidbar, wenn ihr Platz in der Tabelle (z.b. (a,b)) nach Ablauf des Algorithmus leer ist. 3 (z.b. a, b, c) sind voneinander ununterscheidbar, wenn (a,b) und (b,c) leer sind...
aber wenn du zwei leere Stellen (a,b) und (c,d) hast, dann sind a und b ununterscheidbar sowie c und d -> das heißt nicht, dass auch z.b. a und c ununterscheidbar sind. Damit alle 4 ununterscheidbar wären, müsste es noch ein leeres Feld (b,c) geben..
ich hoffe, es kommt rüber, was ich mit dem letzten Absatz sagen wollte...
finyfunny
30-06-2004, 13:23
edit zu spät zu lange gebraucht
Danke für die Erklärung, hab da aber noch zwei Fragen:
1) zwar wenn ich mir jetzt immer die Paare aus der Tabelle anschaue, und ich komm mit einem Wort zu zwei Endzuständen, ist das dann Epsilon?
z.B.
c...Endzustand; b...Normalerknoten
Schau mir jetzt an, wo ich hinkomme:
(b,c)--0--> (c,c) ... EZ,EZ ; folgt daraus jetzt ein Epsilon oder wie?
--1-->(d,d)
wenn du mit einem wort zu jeweils von 2 zustanden in den selben zustand kommst dann kannst du nix über die unterscheidbarkeit sagen da sind sie dann durch diese wort nicht unterscheidbar weil du ja quasi zum selben ergebnis kommst.
bei deinem bsp sind sie übehaupt allgemein nicht unterscheidbar weil du sowohl bei 0 als auch bei 1 jeweils nur in einen bestimmten zustand kommst.
2) Was passiert, wenn ich von einem Zustand mit dem Wort nicht weiterkomme?
(b,d)--0-->(c,c)
--1-->(d,?) .... VOn d komm ich mit dem Wort 1 nirgends hin, was mach ich da?
da hast du schon vorher einen fehler gemacht bei einem deterministische automaten solltest du immer in einen weiteren zustand kommen sollte eigentlich durch delta * sichergestelllt sein. (kann auch blödsinn sein bin mir nicht ganz sicher :engel: )
jetzt noch kurz allgemein zur unterscheidbarkeitstabelle es gibt eigentlich nur 3 möglichkeiten was raus kommen kann die wären:
1) (A,B) --a-->(EZ,NEZ); A und B unterscheiden sich durch das wort a
2)(A,B)--a-->(NEZ,NEZ) A und B unterscheiden sichewenn sich die beiden zustände in die sie übergehen unterscheiden => weiterrechenen mit den beidne NEZ
3) (A,B) --a-->(C,C) A und B unterscheiden sich nicht durch das wort a.
wenn ich blödsinn sag bitte ausbessern thinf ist nicht unbedingt meine stärke :coolsmile bin für jeden hinweiss dankbar.
lg finyfunny :ausheck:
....Ich habe eine weitere frage zu diesem Thema:
Nämlich im Skriptum ist ein gutes Bsp. nur weiß ich nicht wenn ich mit dem ausfüllen der Unterscheid.Tabelle fertig bin. Wie ich die Leeren FELDER zusammenziehe sodass sie minimal ist.
Kann mir da jemand weiter helfen? Bei dem Bsp. im Skriptum geht nämlich die Knoten (e), (d) und (h) weg. Wie gehe ich das an?
mfg KoKo
@ gck und finyfunny
Danke für die Erklärung!
MFG MrAngel
finyfunny
01-07-2004, 12:29
....Ich habe eine weitere frage zu diesem Thema:
Nämlich im Skriptum ist ein gutes Bsp. nur weiß ich nicht wenn ich mit dem ausfüllen der Unterscheid.Tabelle fertig bin. Wie ich die Leeren FELDER zusammenziehe sodass sie minimal ist.
Kann mir da jemand weiter helfen? Bei dem Bsp. im Skriptum geht nämlich die Knoten (e), (d) und (h) weg. Wie gehe ich das an?
naja prinzipell kannst du mal alle kanten weglassen die nicht von startzustand aus erreichbar sind das ist in diesem fall (d) mit denen musst weder was weiteres machen noch sie in der untescheidbarkeitstabelle beachten.
wenn du die tabelle hast hast du ja wenn es nicht unterscheidbare zustände gibt jeweils zustandspaare. von diesen paaren kannst du jetzt einen (egal welche . am besten schaut man welche weniger arbeit ist mit kanten umlegen :devil: ) weglassen . musst aber dabei drauf achten dass keine kanten zu eine anderen knoten der noch gebraucht wird verloren gehen .
so jetzt an deinem bsp:
hier hast due die paare (a) und (e) und (b) und (h) ´:
bei (a) und (e) lässt du einfach (h) weg hier musst du nur eine kannte umlegen nur die 1er kante von (g) nach (e) die lässt du jetzt von (g) nach (a) laufen . bei (a) hättest du einiges mehr arbeit gehabt abgesehen davon dass es der anfangszustand ist :coolsmile . es gibt hier noch eine kannte die von e nach (h) aber die fällt so und so weg da auch (h) wegfällt
bei (b) und (h) lässt man einfach (h) wegfallen das ist besonders angnehm da du hier nichts umlegen musste du due kante die von (e) kommt so und so wegfällt. (b) wäre wiededeutlich müssamer.
bitte ausbessern wenn das blödsinn ist:engel:
lg finyfunny :ausheck:
also ich verstehs noch immer nicht ganz :(
könnte mir einer anhand dieser unterscheidbarkeitstabelle http://www.logic.at/lvas/thinf1/angaben/ti1v031.pdf erklären, wie ich beim Zustand {4} u. {0} auf das BAB komme???
danke
finyfunny
01-07-2004, 14:55
naja ich versuchs mal .
du hast das zustandpaar({4},{0}]) jetzt schau ich mal wohin ich mit einem an wo hin ich mit einem A kommen da komm ich von {0} und von {4} in die {} hier sind sie mal nicht unterscheidbar. formal ({4},{0}])-A->({},{})
dann wohin ich mit einem B komme
({4},{0}])-B->({1,2,3,4},{4}) ; jetzt schaust du in deiner tabelle nach ({1,2,3,4},{4})untescheiden sich durch AB hast du verher schon nachgewiesen daher unterscheiden sich deine beiden zustände jetzt durch das B das du gerade gegangen bist und durch das AB von ({1,2,3,4},{4}).
jetzt hast du dein B+AB ist dann das gesuchte BAB.
du musst solagen die zustandspaare anschauen bis du nicht mehr weiter kommst oder bis sie sich unterscheiden und dan setzt du die worte die du gehts zusammen und kommst auf das endergebnis
ich hoffe das ist halbwegs verständlich erklärt.
lg finyfunny :ausheck:
alles klar, danke für die erklärung! :thumb:
grassi3000
01-07-2004, 19:17
jetzt noch kurz allgemein zur unterscheidbarkeitstabelle es gibt eigentlich nur 3 möglichkeiten was raus kommen kann die wären:
1) (A,B) --a-->(EZ,NEZ); A und B unterscheiden sich durch das wort a
2)(A,B)--a-->(NEZ,NEZ) A und B unterscheiden sichewenn sich die beiden zustände in die sie übergehen unterscheiden => weiterrechenen mit den beidne NEZ
3) (A,B) --a-->(C,C) A und B unterscheiden sich nicht durch das wort a.
Was ist aber wenn ich jetzt zb. habe:
(A,B) --a--> (C,D) EZ,EZ
muss ich hier dann einfach die unterscheidung für (C,D) machen?
und wenn jetzt sowas in der Art rauskommt:
(A,B) --a--> (C,D) EZ,EZ
(A,B) --b--> (E,F) NEZ,NEZ
Was von den beiden muss ich dann weiterbetrachten?
finyfunny
01-07-2004, 19:33
Was ist aber wenn ich jetzt zb. habe:
(A,B) --a--> (C,D) EZ,EZ
muss ich hier dann einfach die unterscheidung für (C,D) machen?
ja genau dann musst du dir (C,D) anschauen
und wenn jetzt sowas in der Art rauskommt:
(A,B) --a--> (C,D) EZ,EZ
(A,B) --b--> (E,F) NEZ,NEZ
Was von den beiden muss ich dann weiterbetrachten
kannst du dir aussuchen ist egal musst irgendwann so und so jedes machen ;) um die tabelle fertig zu bekommen.
nochmal allgemein genauer:
du bist nur dann fertig wenn du
(A,B) --a--> (C,D) EZ,NEZ => unterscheidbar durch a
(A,B) --a--> (C,D) NEZ,EZ => unterscheidbar durch a
oder ( A,B) ---a-->A,A 0 => nicht unterscheidbar durch irgendwas mit a
wenn du
(A,B) --a--> (C,D) EZ,EZ
(A,B) --a--> (C,D) NEZ,NEZ
hast musst du weitermachen .
ich hoffe das ist jetzt klarer
lg finyfunny :ausheck:
grassi3000
01-07-2004, 19:55
oder ( A,B) ---b-->A,A 0 => nicht unterscheidbar durch irgendwas mit adu meintest hoffentlich "nicht unterscheidbar durch irgendwas mit b", oder?
finyfunny
01-07-2004, 19:57
du meintest hoffentlich "nicht unterscheidbar durch irgendwas mit b", oder?ja tut leid kleiner tippfehler :hewa: werds gleich ausbessern
lg finyfunny
grassi3000
01-07-2004, 20:27
Achja,nochwas (ich hoffe ich nerve nicht):
Muss ich die Falle immer in der unterscheidbarkeitstab. drinnen haben?
Und, bei der unterscheidbarkeitstabelle muss ich ja die zustände in der richtigen reihenfolge aufschreiben (zumindest war das bei meiner so, dass sie nur auf eine art und weise funktioniert hat). wie komm ich auf die richtige reihenfolge?
finyfunny
01-07-2004, 21:26
du kannst die falle in die tabelle aufnehmen wenns dich freut ...ist aber nicht notwendig die kann man so und so nicht weglassen die gibts immer :p .ich lass sie immer weg wozu unnütze arbeit.:devil:
ich mach die unterscheidbar keits tabelle immer so wie im skriptum (nenne vorher immer der reihenfolge nach wie sie in delta ^ vorkommen nach dem alphabeth um als A,B....) . ist glaub ich aber prinzipell egal :coolsmile . du musst nur wirklich schauen dass wirklich jedes möglich zustandspaar bist auf paar (A,A) (B,B) ein kästchen bekommt kann sein dass du bei deinem versuch irgendein paar vergessen hast . ....es schadet aber sicher nicht es so wie im skriptum zu machen so stimmts sicher.
lg finyfunny :ausheck:
Achja,nochwas (ich hoffe ich nerve nicht):
Muss ich die Falle immer in der unterscheidbarkeitstab. drinnen haben?
Und, bei der unterscheidbarkeitstabelle muss ich ja die zustände in der richtigen reihenfolge aufschreiben (zumindest war das bei meiner so, dass sie nur auf eine art und weise funktioniert hat). wie komm ich auf die richtige reihenfolge?
Ich machs immer so, dass ich einfach die Reihenfolge aus der Tabelle für Delta^ hernehm, für die senkrechte Spalte alle Zustände bis auf den ersten hinschreib, und für die waagrechte Spalte alle Zustände bis auf den letzten. Eigentlich genau wie im Skriptum. Die Falle kommt auch mit rein, erstens der Vollständigkeit halber, zweites weil ich die auch schon mal gebraucht hab, um Unterscheidbarkeit festzustellen. Ob das damals richtig war oder nicht weiß ich nicht, zumindest hats mit der Lösung im PDF übereingestimmt.
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.