From joe Tue Nov 21 08:58:49 2000 Subject: Re: Konstruktion eines Automaten =?ISO-8859-1?Q?=FCber?= Derivatenbildung Date: Tue, 21 Nov 2000 08:58:49 +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: 1969 Status: RO diese berechnung stimmt nicht: 1 NF (<1><0>) dort ist ein fehler im skript (seite 19 oben), wo genau, finden Sie selbst. was müßte nämlich herauskommen? alle wörter w, für die 1w in 1* 0* ist. das ist doch offensichtlich die sprache 1* 0* selbst. jetzt schauen wir mal, woran das liegt. ich schreibe D_x(L) anstatt x NF L, denn dann sieht es noch mehr wie eine (partielle) ableitung aus. es geht ja um D_x(A . B) mit A = 1*, B = 0* die ableitung eines produkts ensteht durch "ableiten vorne", und die fälle, daß "vorn" das leere wort steht, dann müssen wir "hinten" ableiten: D_x(A . B) = D_x(A) . B + (if epsilon in A then D_x(B) else leer) außerdem brauchen wir D_x(L*). wir machen uns zunächst klar, daß L* = (L - epsilon)* "-" ist mengendifferenz. setzen wir L' := L - epsilon, also L* = L'* dann gilt D_x(L*) = D_x(L'*) = D_x(epsilon + L' . L'* ) nach definition Q* = epsilon + Q . Q* = D_x(epsilon) + D_x(L' . L'*) distributivgesetz = leer + D_x(L') . L'* + (if epsilon in L' then D_x(L'*) else leer) nach produktregel, siehe oben = leer + D_x(L') . L'* + ( leer) weil epsilon nicht in L', siehe oben = D_x(L') . L'* = D_x(L ) . L* weil D_x(L - epsilon) = D_x(L) wenden wir das an: D_1(1*) = D_1(1) . 1* = epsilon . 1* = 1* D_1(0*) = D_1(0) . 0* = leer . 0* = leer und nun die ursprüngliche aufgabe: D_1(1* 0*) = D_1(1*) . 0* + (if epsilon in 0* then D_1(0*) else leer) = 1* . 0* + D_1(0*) = 1* . 0* + leer = 1* . 0* das heißt, im automaten geht vom startzustands 1* 0* ein mit 1 beschrifteter pfeil zum startzustand zurück. -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --