KA04 - Ekvivalentní automaty

Přestože dva konečné automaty obsahují rozdílný počet stavů, rozdílný počet a tvar přechodových funkcí, mohou být ekvivalentní.

Definice 1: Konečný automat A a konečný automat B jsou ekvivalentní, pokud oba rozpoznávají jeden společný jazyk, tedy L(A) = L(B).

Abychom mohli velice jednoduše ověřit, zdali dva konečné automaty jsou ekvivalentní, je zapotřebí nejprve definovat dosažitelnost a nedosažitelnost každého stavu.

Definice 2: Pokud existuje pro daný konečný automat slovo w takové, že pak je stav q dosažitelný. V opačném případě je daný stav nedosažitelný.

Algoritmus nalezení dosažitelných stavů

Použijeme tabulku s definicí konečného automatu.
Označíme počáteční stav (počáteční stavy).
Pro každý označený stav postupně procházíme hierarchii přechodových definic tak, že vždy označíme další stavy, které lze z daného stavu dosáhnout.
Pokud již nevznikají nově označené stavy a prošli jsme celou strukturu konečného automatu, pak všechny označené stavy jsou dosažitelné a všechny neoznačené jsou nedosažitelné.

Na následujícím příkladu si ukážeme algoritmus nalezení dosažitelných stavů v praxi. Mějme následující konečný automat:

Nejprve označíme vstupní stav A:

Vstupní stav je jen jeden, a to stav A. Z něj se pak můžeme dostat pouze do dvou dalších stavů, a to B a D. Oba dva tyto stavy nyní označíme:

Ze stavu B se automat posouvá do stavu D a F, ze stavu D se pak automat posouvá do stavu H a B, přičemž stavy D a B již označeny jsou. Označíme tedy pouze nové stavy, a to F a H: Oba nově označené stavy F a H směřují do již označených stavů, tedy do {D, A} a {B, F}. Z toho vyplývá, že jsme se právě dostali na konec našeho algoritmu. Zeleně označené stavy jsou stavy dosažitelné (A, B, D, F, H} a neoznačené stavy jsou stavy nedosažitelné (C, E, G, I). Všimněte si, že původní počet výstupních stavů klesl z počtu 5 na pouhé dva. Nedosažitelné stavy včetně jejich přechodových funkcí můžeme z konečného automatu vyjmout. Následující obrázek ukazuje výsledek po eliminaci. Tento konečný automat je ekvivalentní tomu původnímu.