614372776

Rysunek 5 przedstawia jeden ze sposób jakie automat z rysunku przechodzi przez poszczególne stany dla ciągu wejściowego 00101. Automat rozpoczyna działanie będąc w stanie go- Po odczytaniu pierwszego symbolu, czyli zera może przejść do stanu go lub gi- Zgodnie z założeniem automat przechodzi do obydwu stanów.

Następnie automat odczytuje kolejne zero. Ze stan go możemy przejść do stanów go albo q\. Jednak stan qi nie przejścia dla zera, więc ten wątek przetwarzania niejako zamiera i może zostać przez automat porzucony. Po odczytaniu trzeciego symbolu 1, należy wziąć pod uwagę przejścia z go jak i q\. Stwierdzić można iż za pomocą symbolu 0 stan go przechodzi na go, podczas gdy q\ przechodzi tylko na q2- Po odczytaniu 001 automat znajduje się w dwóch stanach go oraz g2- Ponieważ g2 jest stanem akceptującym to automat zaakceptuje wejście 001.

001    01

Rysunek 5: Stan, przez jakie może przejść niedeterministyczny automat skończony podczas przetwarzania słowa wejściowego 00101

Wejściowy łańcuch znaków jeszcze się nie skończył. Kolejny symbol 0 powoduje zatrzymanie się wątku g2, ale ze stanu go można przejść do dwóch kolejnych stanów go oraz q\. Ostatni symbol 1, powoduje przejście z go do go oraz gi do g2- Ponieważ ponownie został osiągnięty stan akceptujący, toteż oznacza to iż ciąg 00101 został zaakceptowany.

Na podstawie tego przykładu już łatwo podać tabelę dla funkcji przejścia, jednak tym razem wartościami są zbiory, jeśli z którego stanu nie ma przejścia przy pomocy symbolu zbioru pustego

	1 0 II 1
—* 9o I	I {9o,9i} I	I {9o}
9i	0	{92}
*92 |	0 |	1 ^0

1.3.1 Rozszerzona postać funkcji przejścia

W dość podobny sposób jak dla automatów deterministycznych można rozszerzyć funkcję S automatu niedeter-ministycznego do funkcji <5. Indukcyjna definicja <5 jest również podobna:

Podstawa: S(q,e) = go - czyli, nie zostały odczytane jeszcze żadne symbole, więc stan pozostaje bez zmian. Krok indukcyjny: Jeśli założymy, że w = xa, gdzie o jest końcowym symbolem w, natomiast x resztą słowa w, oraz S(q,x) = {pi,j>2, • ■ • ,Pn) to:

U 5(Pi,a) = {ri,r₂,...,r_m}    (6)

i=l

Wtedy 5(q,w) = {?'i,?'2,... ,r_n}. Można powiedzieć, że wartość funkcji 5(q,w) została obliczona poprzez wyznaczenie S(q,x), a następnie prześledzenie dowolnego przejścia opatrzonego etykietą o.

Dla wejścia 00101 i automatu przedstawionego na rysunku 4 rozszerzona postać funkcji przejścia jest następująca:

1.    ó(q₀,e) = {g₀} ,

2.    (5(go,0) = <5(go,0) = {go,gi} ,

3.    <5(go,OO) = <S(go,O)U<S(gi,O) = {go,gi}U0 = {g_o,gi} ,

4.    <5(go,001) = <5(g_o,l)U<S(gi,l) = {g_o}u{g₂} = {go,g2} ,

5.    .5(g₀,0010) = ń(go,0)Uń(g₂,0) = {go,9i}U0 = {go,gi} ,

6.    <5(g₀,00101) = <5(g₀,l)U<S(gi,l) = {g₀}u{g₂} = {go, 92} ■

6