3813100526

2. A2 = (S2, h,T2) gdzie

•    ^2 = {so,Sl, S2>S3,S4};

•    h = {«o};

•    funkcję przejścia T2 opisuje diagram zilustrowany na poniższym rysunku.

W tym przypadku niedeterminizm objawia się tym, że dla pewnych stanów oraz symboli alfabetu istnieje więcej niż jeden stan w który maszyna A2 może wejść.

Przykład 1.4.

Niech teraz E = {0,1}. Rozważmy maszynę ^3 = (5, {so}, T), gdzie:

•    S = {so,si};

•    funkcję T zilustrowano przy pomocy diagramu przedstawionego na rysunku:

0 1 0

1

Maszyna ^3 jest przykładem maszyny deterministycznej.

1.1.2. Obliczenia skończenie stanowej maszyny na skończonych słowach

Niech A — (S, I, T) będzie niedeterministyczną skończenie stanową maszyną nad alfabetem E oraz niech u = ctq<ti ... cr_m € E* będzie skończonym słowem. Takie słowo, gdy poddane zostaje maszynie A do odczytania, nazywamy też „wejściem” (ang. input).

9