Revision history [back]

Minimální DKA vznikne pouze pokud rozpoznáš při derivování všechny ekvivalentní regulární výrazy.

Pokud v algoritmu dostaneš dva ekvivalentní regulární výrazy, a ty nevíš, zda jsou ekvivalentní, pak se v automatu vytvoří dva stavy, jejichž pravý jazyk bude stejný, tudíž tyto dva stavy budou ve stejné třídě ekvivalence a automat tak nebude minimální (snad jsem to napsal dobře :) ).

Problém, zda dva RV popisují stejný jazyk není algoritmicky vůbec lehký: musíš je oba převést na mDKA a pak porovnat tyto automaty, zda přijímají stejný jazyk. Proto se v praxi toto v Brzozowského metodě derivací většinou nedělá, ale výrazy se buď vůbec nekontrolují, nebo se kontrolují na tzv. podobnost, což není nic jiného, než aplikace pár základních axiomů (BI-AAG 2014, př. 4, slajd 4/28), pomocí kterých možná o ekvivalenci budeš moci rozhodnout.

Minimální DKA vznikne pouze pokud rozpoznáš při derivování všechny ekvivalentní regulární výrazy.

Pokud v algoritmu dostaneš dva ekvivalentní regulární výrazy, a ty nevíš, zda jsou ekvivalentní, pak se v automatu vytvoří dva stavy, jejichž pravý jazyk bude stejný, tudíž tyto dva stavy budou ve stejné třídě ekvivalence a automat tak nebude minimální (snad jsem to napsal dobře :) ).

Problém, zda dva RV popisují stejný jazyk není algoritmicky vůbec lehký: musíš je oba převést na mDKA a pak porovnat tyto automaty, zda přijímají stejný jazyk. Proto se v praxi toto v Brzozowského metodě derivací většinou nedělá, ale výrazy se buď vůbec nekontrolují, nebo se kontrolují jen na tzv. podobnost, což není nic jiného, než aplikace pár základních axiomů (BI-AAG 2014, př. 4, slajd 4/28), pomocí kterých možná o ekvivalenci budeš moci rozhodnout.