Pok-2-wyk-Slajd16

Automaty skończone

Języki regularne mogą być rozpoznawane przez automaty skończone, czyli automaty o skończonej liczbie stanów. Przejdźmy więc do definicji automatów skończonych.

Niedeterministycznym automatem skończonym (w skrócie NAS) nad alfabetem A nazywamy system M składający się z:

• Wspomnianego już alfabetu A,
• Zbioru stanów S
• Funkcji przejść f odwzorowującej alfabet A na zbiór stanów S
• Stanu początkowego s0

oraz

• Zbioru stanów końcowych T (nazywanego również zbiorem stanów akceptujących).

<< Poprzedni slajd | Spis treści | Następny slajd >>