Testangaben 23.10.2003, Grp.A, Bsp.3

[maitscha]

Testangaben 23.10.2003, Grp.A, Bsp.3: Aus welchen Überlegungen ergibt sich dieser deterministische Automat laut Lösung?

[Plantschkuh!]

Der Automat aus der Angabe ist bereits deterministisch; wir wollen einen äquivalenten minimalen finden.
Dazu wird die Unterscheidbarkeitstabelle aufgestellt. Man erkennt, daß alle Felder ausgefüllt sind, also sind keine zwei Zustände voneinander ununterscheidbar (d.h. jeder Zustand ist von jedem anderen unterscheidbar), man kann also keine Zustände verschmelzen. Der Automat ist also auch schon minimal; die Angabe ist bereits die Lösung!
Die graphische Darstellung ergibt sich einfach aus der Tabelle der Übergangsfunktion, wobei der Zustand 5 eingespart wurde, da er nichts anderes als die Falle ist (das muß man anscheinend nicht gesondert beweisen, dazuschreiben wäre aber zumindest gut).

[maitscha]

Da der 5. Zustand die Falle ist, kann man ihn einfach weglassen?

[gck]

Da der 5. Zustand die Falle ist, kann man ihn einfach weglassen?
Wenn du den Automaten zeichnest, kannst du die Falle weglassen: dadurch gibt es nun manche Zustände, von denen man mit gewissen Symbolen nicht mehr weiterkommt -> "eigentlich" würdest du mit diesem Symbol in die Falle kommen, aus der du nicht mehr rauskommst. Die Falle ist nur deshalb da, damit die Übergangsfunktion total ist (also dort, wo sie nicht total wäre, weil für ein gewisses Symbol kein Zielzustand möglich ist, dann machst du für dieses Symbol einen Übergang in die Falle, und von der Falle führen alle Übergänge wieder in die Falle -> damit ist die Übergangsfunktion total, aber es werden immer noch keine Wörter akzeptiert, die vorher nicht akzeptiert worden sind).

In der Unterscheidbarkeitstabelle kann man die Falle aber generell nicht weglassen, auch nicht in der Übergangsfunktion (dann wäre die ja wieder nicht total und das ganze Spiel mit der Falle wird ad absurdum geführt).

Dass ein Zustand eine Falle ist, ist genau dann der Fall, wenn er 1. irgendwie erreichbar ist und man 2. nicht mehr daraus herauskommt.

[oopster]

Der Automat aus der Angabe ist bereits deterministisch; wir wollen einen äquivalenten minimalen finden.
Dazu wird die Unterscheidbarkeitstabelle aufgestellt. Man erkennt, daß alle Felder ausgefüllt sind, also sind keine zwei Zustände voneinander ununterscheidbar (d.h. jeder Zustand ist von jedem anderen unterscheidbar), man kann also keine Zustände verschmelzen. Der Automat ist also auch schon minimal; die Angabe ist bereits die Lösung!

dürfen wir das auch so schnell machen, wenn wirs sehen, oder müssen wir ne kompletten nachweis erbringen (Unterscheidbarkeitstabelle,...)

lg

[Lynx]

Das muss man bei der Prüfung auf jeden Fall beweisen. Genau genommen kannst du ja, bevor du deine Unterscheidbarkeitstabelle aufgestellt hast, ja noch gar nicht wissen, dass der Automat minimal ist (es kann leicht sein, dass man "mit freiem Auge" nicht sieht, dass sich ein Automat noch minimieren lässt).

[Plantschkuh!]

Außerdem steht bei solchen Beispielen (wie auch bei diesem) immer, und aus gutem Grund, explizit dabei, daß man die Unterscheidbarkeitstabelle angeben muß. Ganz prinzipiell gilt, wie schon in der Übung: Wenn wir für irgendwas ein formales Verfahren gelernt haben, dann ist das auch mit diesem formalen Verfahren zu lösen und nicht durch Hinsehen.