Vlastnosti KA vytvoreneho z RV - metoda derivaci

asked Dec 29 '14

171 ●6 ●9 ●16

Chcel by som sa opytat ako je to s vlastnostami KA vytvoreneho pomocou metody derivacii? V poznamkach z cviceni som si nasiel ze je vzdy DKA, moze byt aj minimalny (nie vsak obecne pre kazdy). V definicii sa zase nic o jeho vlastnostiach nehovori (len ze na vystupe z algoritmu je KA). V rozstreloch na otazku co vznike po metode derivacii je za spravnu odpoved oznacene aj minimalny KA (zdroj je fit-wiki takze spravnost neni 100%).

Vedel by mi niekto dat na toto jednoznacnu odpoved?

Comments

Vždy ti vznikne DKA, to je jasné. S minimálností by to mělo být imho tak, že když se ti korektně podaří zjistit všechny "podobnosti" při derivovaných výrazech (tedy každý výraz, který ti vznikne upravíš na nějaký, který již máš - pokud to jde), tak vznikne minimální. Víc k tomu nevím.

Jan Rubín (Dec 29 '14)

add a comment

answered Dec 29 '14

Tomas Pecka
64 ●2 ●6

updated Dec 29 '14

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 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.

link

Comments

Jasne, takze podobnostou vyrazov si mozem pomoct na to, aby som zistil ci $h(x)=h(y)$ Z niektorych to pojde po upravach ale istotu mam len z mDKA pre kazdy ten RV ktory porovnavam. Kazdopadne ako by ste sa postavili k tej otazke, co je vysledkom metody derivacii? Ja to chapem tak, ze ten vysledny KA musi mat pre kazdy pripad garantovane vlastnosti a tam mDKA obecne nepatri.

Lukas Nagy (Dec 29 '14)

No, vyjde DFA. Vezmi si ten algoritmus ze slajdů a aby byl výsledný automat deterministický, pak: 1. Automat musí mít právě jeden počáteční stav: Splněno, protože počáteční stav odpovídá původnímu regulárnímu výrazu. 2. |\delta(q, a)| <= 1. Splněno - pro každý regulární výraz (odpovídající stavu automatu) a jeden symbol abecedy vznikne derivací jeden regulární výraz, který bude odpovídat zase jen jednomu stavu - vytvořím tedy jen jeden přechod pro každou dvojici (q \in Q, a \in T). Podle \varepsilon nederivuju, takže epsilon přechody nebudou. (Pokud bych chtěl, můžu samozřejmě z derivace dostat dva ekvivalentní RV a k nim tedy přiřadit 2 stavy a do každého tedy natáhnout hranu. Výsledný automat pak nebude ani minimální ani deterministický. Tohle ale není v algoritmu, jen tu spekuluju.)

Tomas Pecka (Dec 30 '14)

Jasne, rozumim ze DFA bude vzdy, ak sa dodrzi algoritmus a nebudem si tam pridavat dalsie veci. Narazam na to, ze na fit-wiki je mDFA oznacene ako spravna odpoved v rozstrele a chcel som sa presvedcit o tom, ze to spravne nema byt.

Lukas Nagy (Dec 30 '14)

add a comment

Vlastnosti KA vytvoreneho z RV - metoda derivaci

Comments

1 Answer

Comments

Your answer

Question tools

Stats

Related questions