3813100535

Prześledźmy działanie procedury z dowodu twierdzenia 1.18 przekształcającej niedeterministyczny automat skończony w deterministyczny automat skończony na przykładzie automatu JC₂ z przykładu 1.17. Przypomnijmy, że K₂ ma następujący diagram przejść:

a, b

Zgodnie z konstrukcją przedstawioną w dowodzie twierdzenia 1.18, deterministyczny automat skończony równoważny niedeterministycznemu automatowi skończonemu K.2 jest następujący:

K, = (A, F'), gdzie:

1.    A = {S\ {/},T).

2.    S' = {0, {S₀}, {Si},{s₂},{SO,Sl},{SO,S₂},{Si,S₂}, {SO,Sl, S2}}-

3.    I G S' jest stanem początkowym.

4.    Funkcja przejścia T jest opisana za pomocą diagramu 1.3.

Rysunek 1.3:

Proces tworzenia diagramu 1.3 zilustrujemy na kilku przykładach.

Ze stanu {so} poprzez symbol „a” automat IC₂ przechodzi do stanu {si}, ponieważ w /C₂ strzałki z etykietą „a” od stanu so prowadzą tylko do stanu Si-Dla automatu /C₂ nie istnieje przejście poprzez symbol „6” od stanu sq zatem w

18