3813100534

będzie obliczeniem 1C na u takim, że

(1.4)

S_m+1 € F'.

Z definicji obliczenia,

V* € {0,..., m} T{Si,<Ji) = S_i+1.

Indukcyjnie, indukcją na i € {0,..., m + 1} zdefiniujemy ciąg stanów z S

s_ks_k+i...s_m+i, gdzie k = m + 1 — i

taki, że:

1)    Sm+i € F oraz

2)    s_J+i £ T(sj,<jj) dla dowolnego j £ {k,k + 1,..., m} i

3)    Sj £ Sj, dla dowolego j £ {k,..., m + 1}.

Gdy taki ciąg zostanie zdefiniowany dla każdego i £ {0,... ,m + 1}, to dla i = m + 1, otrzymamy: k = 0 i ciąg so ... s_m+i spełnia warunki 1) - 2), mianowicie:

Sm+ieF, Vj € {0,    Sf₊₁ e T(sj,crj).

Będzie więc to obliczenie akceptujące słowo u przez IC, co zakończy dowód, że u £ C(JC).

Aby uzupełnić dowód wystarczy więc teraz podać indukcyjną definicję ciągu s_k ... s_m+i, dla k = m + 1 — i, spełniającego warunki 1) - 3).

Zauważmy najpierw, że skoro na mocy (1.4) S_m+\ £ F¹, to z definicji F', S_m+1nF / 0. Niech więc, dla i = 0, s_m+i będzie dowolnym elementem niepustego zbioru S_m+i D F. Wtedy warunek 1) jest oczywisty, jak również warunek 3) dla j = m + 1. Ponieważ k = m + 1, to warunek 2) jest pusto spełniony.

Przypuśćmy teraz, że dla pewnego i £ {0,..., m} i dla k = m + 1 — i ciąg s_k...s_m+1 spełniający 1) - 3) został już zdefiniowany. Zdefiniujemy stan s_k-\. Zauważmy, że k — 1 = m + l — i — 1 = m — i ^ m. Z 3), s_k £ S_k. Ale, ponieważ k — 1 ^ m, to z definicji K.,

Sk = U T(s,0 k-i)-

seSk-i

Stąd s_k £ U T(s, (7fc_i), więc 3s £ 5fc_i taki, że Sfc £ T(s, (Tfc_i).

seSfc_i

Niech s_k-i będzie takim s. Wtedy s_k £ T(s_k-i,cr_k-i) oraz s_k-1 £ <Sfc_i. Zatem ciąg s_k_i... s_m+ \ spełnia warunki 1) i 2). Warunek 3) pozostaje spełniony, z założenia indukcyjnego.

□

Przykład 1.19.

17