614372767

automatu D w taki sposób aby dla Sp(q, a) = p, funkcja przejścia automatu niedeterministycznego E miała postać <5e(<7, a) = {p}. Po tej zamianie przejścia są takie same ale brakuje jawnych ^-przejść. Nie stanowi to jednak o żadnym błędzie, czy niedopatrzeniu.

Druga implikacja => dla automatu niedeterministycznego E = {Qe,^,Se,Qo, Ep} z e-przejściami wymaga zastosowania zmodyfikowanej konstrukcji podzbiorów aby otrzymać D = {Qp,^, Sp, qp, Fp}. W ten sposób chcemy wykazać iż L(D) = L(E). W tym celu należy wykazać równoważność rozszerzonych funkcji przejścia Oe(qo»*o) = ^p(qp,w), za pomocą indukcji po długości słowa w.

Podstawa: Jeśli |w| = 0, to naturalnie w = e. Wiemy, że 6e(qo,^e) ⁼ ED(ąą). Natomiast stan początkowy został zdefiniowany jako qp = ED(</o) • Ostatecznie wiadomo, że dla dowolnego deterministycznego automatu Sp (p, e) = p dla dowolnego stanu p, a więc w szczególności Sp (qo,e) = ED(<j₀). Co kończy pierwszą część dowodu iż Ś_E(q₀,£) = 5p(qp,e).

Krok indukcyjny: Niech słowo w = xa, gdzie a jest ostatnim symbolem. Zakładamy, że rozważane twierdzenie jest prawdziwe dla x. Oznacza to, że ós(qo,x) = Sp(qp,x) a wartością obydwu funkcji niech będzie zbiór {pi,P2,... ,Pfc}. Korzystając z definicji S dla automatu niedeterministycznego z przejściami e będziemy obliczać wartość funkcji S_E(qo, w) w następujący sposób:

1- Ui=i 6e(Pu a) = {r-1, r₂,..., r_m},

2. ń_£(9o,w) = Ur=i^ED(^ł’i)-

Odwołując się w tym miejscu do konwersji automatu niedeterministycznego na deterministyczny bez e-przejść, zobaczymy że 5p{{pi, P2, • • • ,Pfc},a) konstruuje się za pomocą dwóch kroków wymienionych powyżej. Co pozwala stwierdzić, że Sp(qp,w), jest tożsama z <$d({pi,P2, • • ■,P/c},^a) oraz ze zbiorem generowanym przez S_E(qo,w). W ten sposób dowiedziono, że óp(qo>w) = 8p(qp,w). □

3 Wyrażenia regularne

Niech E będzie skończonym zbiorem symboli i niech L, L\, L2, będą zbiorami łańcuchów z E*. Złożeniem L\, L2, oznaczanym L1L2, nazywamy {xy \ x € L\, y € £-2}. Innymi słowy, łańcuchy należące do L1L2 są tworzone poprzez wszystkie kombinacje elementów z łańcucha Li z elementami łańcucha L2. Niech L° = {A} i L' = LL^1-1 dla i > 1. Domknięciem Kleene’go L oznaczonym przez symbol L’, nazywamy zbiór:

L' = \jL‘

i=0

Natomiast domknięciem dodatnim L, oznaczonym symbolem L⁺, jest zbiór:

i+=Qi'

Inaczej mówiąc zbiór L* to wszystkie słowa po złożeniu dowolnej liczby słów z L. Podobnie zbiór L⁺ jednak nie zalicza się tu słów pustych z elementem A.

Przykład 1 Niech Li = {10,1} oraz L₂ = {011,11}. Wtedy L_tL₂ = {10011,1011,111}. Ponadto {10,11}* = {A, 10,11,1010,1011,1110,1111,...}

Niech E będzie alfabetem. Wyrażenia regularne nad zbiorem E są zdefiniowane w następujący sposób:

1.    0 jest wyrażeniem regularnym reprezentującym zbiór pusty

2.    A wyrażeniem regularnym reprezentującym zbiór {A}

3.    Dla każdego a € E, a jest wyrażeniem regularnym reprezentującym zbiór {a}

4.    Jeżeli r i s są wyrażeniami regularnymi reprezentującymi języki R i S to (r+s) (alternatywny zapis (r|s)), (rs), (r*) są wyrażeniami regularnymi reprezentującymi odpowiednio zbiory R U S, RS i i?*.

14