3813100533

1.    S' = V(S);

2.    T : S' x £ —> S' jest taka, że

dla dowolnego X G S', a G £, kładziemy T(X,a) := [J T(s,ij);

3.    F' = {X C S \ X HF ź®}.

Dla wszystkich X i a, T(X, a) istnieje i jest jedyne, więc T jest rzeczywiście funkcją: T : S' x £ —» S'. Ponadto, ponieważ zbór stanów początkowych ma jeden element, to zdefiniowany przez nas automat jest DFA.

Pokażemy, że L{K) = L(K,).

(C)    Niech u = cto^i • • • G_m € £* będzie słowem akceptowanym przez K. Istnieje zatem obliczenie r = sqS\S2 ■ ■ ■ s_m+i niedeterministycznego automatu skończonego K. na u takie, że

%+l € F    (1.1)

oraz

Vś G {0,..., m} Si+i G T(si, <Ti).    (1.2)

Definiujemy indukcyjnie zbiory Si, i = 0,..., m -f 1:

f S₀:=I

) Si+i := T(Si, (Ti) — U T(s, <7i) dla i<m l    s€Si

Indukcyjnie pokażemy, że = 0,..., m 4-1 Si G Si.

Ponieważ r jest obliczeniem, to so G I = Sq. Załóżmy, że dla pewnego i < m Si G Si. Wtedy

1)    Sf+i G r(sj,£7j), na mocy (1.2);

2)    T(si, ai) c u r(_s,<T_i)⁽=^>5_<+1.

seSi

Stąd Sj+i G Si+\. Na mocy zasady indukcji matematycznej V i ^ m Si G Ą, a zatem Sm+i € Sm+i •

Ponieważ s_m+i G F, to 5_m+i fi F 7^ 0. Stąd S_m+i G F¹. Ciąg So ■ • • S_m-|-i

spełnia definicję obliczenia akceptującego automatu K, na słowie u, a zatem u G £(£).

(D)    Niech teraz słowo w = cro&i ■ ■ ■ G_m £ £(£) oraz niech ciąg stanów z S"

... S_m+1

16