Pok-2-wyk-Slajd24

NAS – Niedeterministyczny Automat Skończony

Warto zwrócić uwagę na dwie istotne charakterystyki niedeterministycznych automatów skończonych.

Otóż dopuszczają one możliwość przejścia pod wpływem jednego symbolu wejściowego do więcej niż jednego stanu.

Sytuacja ta przedstawiona jest na grafie przejść dla wyrażenia (a|b)*abb. Proszę zwrócić uwagę na przejścia ze stanu s0 pod wpływem symbolu „a”. Przejście może nastąpić do stanu s0 lub do stanu s1.

Drugą istotną cechą automatów NAS jest istnienie epsilon-przejść, czyli zmian stanu występujących bez konieczności pobrania kolejnego symbolu z wejścia. Sytuacja taka będzie zobrazowana na następnym slajdzie.

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