From joe Mon Nov 20 09:18:59 2000
Subject: Re: Fragen =?ISO-8859-1?Q?=FCber?= Fragen
Date: Mon, 20 Nov 2000 09:18:59 +0100 (MET)
X-Mailer: ELM [version 2.4ME+ PL61 (25)]
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Content-Length:  2053
Status: RO


> 1) Finden von äquivalenten Zuständen (S.23):
> 	und zwar finde ich es ziemlich aufwendig alle Wörter der Länge i
> durchzuprobieren 

wenn man es ohne maschinelle hilfe macht, erscheint manches aufwendig.
was dort steht, ist eben die definition, und die sollen Sie beherrschen.
die übungs- und testat- usw.- aufgaben machen wir schon so,
daß wir es auch in endlicher zeit korrigieren (d. h. Sie auch
in endlicher zeit hinschreiben) können.


> bzw. denke ich das das finden von den Zuständen so wie wir
> es im Seminar gemacht haben auch nicht sehr sinnvoll/unübersichtlich 

soso. ich finde es sinnvoll, weil das korrekte ergebnis rauskommt.
ich hab das auch mal "wirklich" implementiert, siehe
http://www.informatik.uni-leipzig.de/~joe/rx/src/FAmin.hs
das werden Sie auch in keinem lehrbuch anders finden.

> Ein - und Abgangspfeile von Knoten (Zuständen) aufzuschreiben und dann
> nachzuschauen welche übereinstimmen.
...
> -(z0;	0(0), 0(1)	;0(0), 1(1))
> -(z1;	1(1)		;0(1), 1(0))
...

dabei ignorieren Sie doch völlig, zu welchen zuständen die pfeile gehen?
das wird doch im allgemeinen nicht gutgehen.


> 2)Die Relation ~A (S.24) [p] = {q | p ~A q} und p ~A q gdw. f(p, z0) = f(q,
> z0)
> 	d.h für mich das [p] die Menge aller Wörter q sind die mit p in ~A relation
> stehen
> 	Warum ist dann (€-leeres Wort) [€] = z0 ein Zustand? wenn eigentlich eine
> Menge mit nur 	Wörtern rauskommen soll? bzw. Z - Zustandsmenge; Z = { [p] |
> p Element X}

vorsicht, genau hinsehen: in den letzten drei zeilen der bemerkung c)
wird ein neuer automat konstruiert (der sollte lieber A' heißen),
dessen zustände die äquivalenzklassen bezüglich ~A sind.
der startzustand ist die klasse von epsilon, usw.
die behauptung ist dann, daß der neue automat A' wieder genau L akzeptiert.

in bemerkung a) seite 26 steht, daß dieser automat sogar der
(eindeutig bestimmte) minimale deterministische automat für L ist.


-- 
-- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
-- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --