Automat Skończony
Automat skończony definiowany jest na ogół jako piątka , gdzie
• jest skończonym zbiorem stanów,
• jest skończonym zbiorem symboli wejściowych (alfabetem),
• jest funkcją przejść,
• jest stanem początkowym,
• jest zbiorem stanów końcowych.
Tak zdefiniowany automat po otrzymaniu ciągu wejściowego (napisu) złożonego z symboli ze zbioru w stanie początkowym ,,czyta'' kolejne symbole napisu i zmienia odpowiednio stany zgodnie z funkcją . W każdym kroku, jeśli aktualnym stanem jest i aktualnym symbolem wejściowym jest , następny stan jest wyznaczony przez . Dotyczy to oczywiście tylko automatów deterministycznych, do których się tu ograniczamy. W przypadku automatów niedeterministycznych wartością jest zbiór możliwych następnych stanów. Jeśli po przetworzeniu całego napisu wejściowego automat znajdzie się w stanie ze zbioru , mówi się, że automat rozpoznał lub zaakceptował ten napis. Zbiór napisów rozpoznawanych przez automaty skończone jest zbiorem wyrażeń regularnych nad alfabetem wejściowym. Zbiór wszystkich możliwych napisów (rozpoznawanych i nie) nad alfabetem wejściowym oznacza się jako .
Możemy powiedzieć, że powyższy sposób zdefiniowania automatu skończonego odpowiada perspektywie lingwistycznej. Jeśli chcemy za pomocą automatu skończonego identyfikować (modelować) nie tyle pewien język, co pewien złożony system, taki jak środowisko, wygodniej jest mówić o akcjach zamiast o symbolach wejściowych (wykonywanie akcji zmienia stan środowiska). Często w definicji uwzględnia się wówczas, zamiast zbioru stanów końcowych, alfabet wyjściowy i funkcję wyjść , która każdemu stanowi przyporządkowuje wyjście (jest to tzw. automat Moore'a; w automacie Mealy'ego wyjścia są związane z przejściami). Tę drugą perspektywę będziemy nazywać perspektywą identyfikacji. Oczywiście oba podejścia stają się równoważne, jeśli -- stany, w których uzyskuje się np. wyjście możemy uznać za końcowe
⠀ CICHOSZ, Pawel. Uczenie się automatów skończonych. Uczenie się maszyn: wykład 11. Retrieved from http://staff.elka.pw.edu.pl/~pcichosz/um/wyklad/arch/wyklad11/wyklad11.html