Pok-2-wyk-Slajd27
Z Studia Informatyczne
NAS -> DAS
Dla każdego niedeterministycznego automatu skończonego istnieje równoważny mu deterministyczny automat skończony.
Slajd przedstawia dwa równoważne automaty skończone dla wyrażenia regularnego a(b|c) zbudowanego nad alfabetem „a”, „b”, „c”.
Po lewej stronie znajduje się niedeterministyczny automat skończony. Proszę zwrócić uwagę, że ze stanu „s0” wychodzą dwie krawędzie zaetykietowane symbolem „a”. Jedna prowadzi do stanu „s1” podczas gdy druga do stanu „s2”.
Po prawej stronie znajduje się deterministyczny automat skończony. Niejednoznaczność występująca w NAS została tu usunięta. Ze stanu „s0” wychodzi jedna krawędź zaetykietowana symbolem „a” i prowadzi do stanu „s13”.
