Beweise, dass für jede reguläre Sprache ´L sube T^(**)´ und jeden Buchstaben ´a in T´ auch ´d_l^a (L) = {w | aw in L}´ regulär ist.
Es sei ´A = (T, Z, z_0, F, delta)´ der endliche Automat, der ´L´ akzeptiert. Wir konstruieren den Automaten ´A'´, der sich von ´A´ nur dadurch unterscheidet, dass er einen neuen Anfangszustand ´z_0^'´ hat, und der in ´z_0^'´ beim Lesen eines Buchstaben ´b´ in den Zustand geht, in den ´A´ beim Lesen von ´ab´ geht. Danach wird wie in ´A´ weitergearbeitet. Der neue Automat ´A'´ erreicht nach Lesen von ´b_1 b_2 … b_n´ also den Zustand, den A nach Lesen von ´a b_1 b_2 … b_n´ erreicht. Folglich gilt ´T(A') = {w | aw in T (A)}´. Dies stimmt aber nur für ´w != lambda´ nach obiger Argumentation. Es ist also ´z_0^'´ noch als akzeptierenden Zustand hinzu zu nehmen, wenn ´a in T(A)´ ist.
´A' = (T, Z uu {z_0^'}, z_0^', F', delta')´ mit ´z_0^' !in Z´
und
´delta'(z_0^', x) = delta(z_0, ax) " für " x in T´ ´delta'(z, x) = delta(z, x) " für " z in Z, x in T´
und
´F' = {(F, "falls " a !in T(A)), (F uu {z_0^'}, "falls " a in T(A)):}´
HPI, 2014-04-29, Theoretische Informatik 2, Blatt 4, Aufgabe 2
2014-07-21 23:04:19 UTC
2014-07-21 23:04:19 UTC