Matematické Fórum

↑ Kondr:
Dikec,ale nemohl bys tady prosim uvest vic rozepsane reseni tohoto problemu,mam to zpracovat jako referát a vůbec nevím,jak na to:-(

↑ Kondr:
Ok.Zatim dik,urco se jeste ozvu;-)

↑ andrééé:Nejprve se přechodová funkce doplní tak, aby byla totální. Pak se automat redukuje. Teorie k tomu začíná definicí 2.34, pěkně je to pak vidět na příkladě 2.40 v odkazvaných skriptech. Jde o to, že se snažíme postupně co nejjemněji rozlišit, které stavy jsou různé. Na začátku je rozdělíme na přijímající a ostatní, to budou skupiny I a II. Pak každou skupinu rozdělíme podle toho, do jaké skupiny stavů z ní vedou přechodové funkce. S dělením skončíme v okamžiku, kdy pro každý symbol v každé skupině každé dva stavy mají stejnou hodnotu přechodové funkce (hodnotu teď bereme z hlediska skupin, ne konkrétních stavů). Z toho příkladu ve skriptech je to fakt vidět, popsat to teoreticky a přitom neformálně mi nějak nejde.

↑ andrééé:Použijeme rekurzivní proceduru AUTOMAT, která pro regexp R udělá toto:
1) je li R tvaru G*, kde G je regexp a * značí iteraci, pak zavolá proceduru AUTOMAT na G, z výsledného automatu pak vyrobí automat přijímající G*
2) je-li R tvaru G+H, kde G,H jou regexpy, zavolá proceduru AUTOMAT na G, následně na H a z výsledných automatů vyrobí automat pro sjednocení
3) je-li R tvaru G.H, kde . značí zřetězení, zavolá proceduru AUTOMAT na G, následně na H a z výsledných automatů vyrobí automat pro zřetězení
4) není-li R ani v jednom z předchozích tvarů, pak je R buď prázdné nebo jednoznakové slovo a automat pro něj sestavíme snadno.

Poněkud vágně jsem použil slovo "vyrobí". Jak je to myšleno přesně se dočteš v těch skriptech ve větách 2.49, 2.52 a 2.53.

"Kanonický" znamená, že vstupní stav má číslo 1, stav, do kterého se z něj dostaneme prvním symbolem abecedy má číslo 2, druhým do stavu číslo 3, .... asi je to to samé, jako normalizovaný.

Totální přechodová funkce znamená, že pro všechny stavy a pro všechny symboly je určeno, do jakého stavu má automat přejít. Tedy pokud to pro nějaký symbol definováno nebylo, doplníme stav "peklo" a všechny nedefinované přechody namíříme do pekla. Pochopitelně z pekla se všemi symboly dostaneme zase do pekla.

↑ andrééé:Ano, rozumíš tomu dobře. Doplnění přechodové funkce na totální to je to vytvoření "pekla", jak jsem psal výše.

Z Tvého odkazu plyne, že redukce je součástí minimalizace. Tak, jak je v odkazovaném materiálu minimalizace popsaná, je v ní i normalizace. Stačilo proto říct, že vytvoříme automat pro regulární výraz, oba automaty zminimalizujeme a porovnáme. Já jsem to ale rozepsal do dvou kroků, které jsem označil jako "optimalizaci" a "převod na kanonický tvar". Měl jsem na mysli redukci a normalizaci podle odkazované terminologie. Zapomněl jsem ale zmínit odstranění nedosažitelných stavů, to je také důležité. Odstranit nadbytečné stavy zvládne redukce.