Matematické Fórum

Bod 1. můžeš přeskočit -- když v zadání píšou že dostaneš regulární výraz, tak už nemusíš ověřovat, že je regulární (stejně tak neověřuješ, že A je utomat).
Jinak myšlenka dobrá, konkrétní realizace popsána v několika příspěvcích zde:
http://forum.matweb.cz/viewtopic.php?id=7350

Porovnání automatů se provede tak, že se oba minimalizují a převedou na kanonický tvar, u vás se tomu tuším říká normalizace. Tedy vstupní  stav má číslo 1, stav, do kterého se z něj dostanu prvním symbolem abecedy 2, druhým symbolem 3,..., pak se podobně očíslují stavy, do kterých se umíme dostat ze stavu 2 atd. Platí, že automaty jsou ekvivalentní <=> jsou jejich kanonické tvary stejné.

a jeste jeden dotaz pro uplnost:
- v podstate resim problem zdali zadany automat A a regularni vyraz gama, prijimaji stejna slova nad abecedou L? Chapu to dobre? Nebo ta terminologie je jinak?

jeste jeden dotaz, kdyz sestrojuji konecny automat k regularnimu vyrazu, tak je volana procedura AUTOMAT, pod tim si mam predstavit co? :) To je jako nejaky program? Nebo to je nejaky automat? ... :) Nebo?

↑ Kondr:
Jak trivialne porovnat zdali dva DKA prijimaji stejna slova nad zadanou abecedou. Chtel bych se ujistit jestli premyslim spravne. Kdyz mam tedy dva DKA, ktere jsem sestrojil pomoci predchozich bodu 1~3 (viz. prvni prispevek), tak potom pomoci Modularniho navrhu zkonstrujuju novy automat A, a to tak ze A= L(A1)L(A2).
Q = Q1 x Q2
((q1,q2),a) = (1(q1,a), 2(q2,a)) pro vsechna q1Q1, q2Q2, a
q0 = (q01, q02)
F = (F1 x Q2) (Q1 x F2)

Potom tedy kdyz sestrojim jeden automat tak rozpoznam hned jestli dane slovo prijme ci ne, a tim i odpovim na otazku zdali dany DKA a RV prijimaji stejna slova.

Je tahle uvaha spravna?
Dekuji za help.

↑ Kondr:Myslel jsem ze kdyz sestrojim prunik dvou automatu, tak vlastne najdu slova ktere prijmou oba automaty.
Chtel bych jenom ted dokazat jestli dane slovo prijmou oba automaty nebo ne. Mam tedy ten obecny postup spravne? Docetl jsem se ve skriptech ze F by melo byt F = (F1 x F2). Tak ted nevim jestli postupuju spravne?

↑ marros11:Jeden automat přijímá množinu slov A, druhý B. Potřebujeme, aby všechna slova z A byla v průniku A,B a podobně aby v něm byla všechna slova z B. Nestačí ten průnik sestrojit, musíme ho s něčím porovnat. Ověřovat, že je ale ještě horší, než ověřovat A=B.

↑ xxsawer:To vypadá taky rozumě, akorát o algoritmu na porovnání dvou regulárních výrazů moc nevím. Celkem mě překvapuje, že to vede na soustavu rovnic.

Uz jsem ztoho uplne mimo. Byl jsem znova na konzultaci a bylo mi receno ze se mam zamyslet nad resenim kdyz mam dva DKA, a mam jednoduse porovnat, zdali prijimaji stejna slova. Napadlo mne sestrojit novy automat a to

Tenhle novy automat bude prijimat jen ty slova, ktere prijme puvodni automat A1 i A2. A tim dokazu ze pro dane slova jsou automaty ekvivalentni, tedy ze prijimaji stejna slova.

Proto F = (F1 x F2).

Je tenhle postup spravny?

↑ xxsawer:Rad bych pouzil tvuj navod, ale dostal jsem za ukol to resit skrze ty dva DKA. Nemuzu proto sestrojit regularni vyrazy :(( V mym pripade neresim konkretni pripad, ale obecny postup.... jsem uz na dne a vubec nevim jak dal.... :( Profesor porad dokola mi opakaval ze existuje trivialni zpusob jak porovnat jestli dva DKA prijimaji stejne slova... ale tim ze to tu resime uz pekne dlouho tak fakt netusim co je mysleno tim trivialni a vse co mne napadne konci ve slepe ulicce :(((

↑ marros11:

Hele podle mě řešíš kraviny...
Neodpověděl si mi na otázku, máš napsat program (v cečku, javě, pascalu...), kterej bude řešit tu úlohu nebo máš jenom vymyslet postup???
Jestli si dostal nějaký zadání, tak je jenom na tobě jak ho vyřešíš, bez ohledu na to co ti doporučil na konzultaci -> já bych to řešil tak jak sem ti poradil výš...
Jestli trváš na tom, že chceš porovnávat dva konečný automaty tak moje rada je tahle:



Co to znamená? Vypadá to možná trochu šíleně, ale neni na tom nic težkýho, je to vlastně podstata důkazu pumping lemmy pro regularní jazyky.
Na začítku si ve stavu q0 (teda počátečnim stavu) a chceš zkusit jestli ten automat přijme řetězec w. Představ si, že ten řetězec je hodně dlouhej a dá se rozložit na tři podřetězce xyz. (To je ta druhá závorka). Teď ten automat přijme řetězec x a dostane se do nějakýho stavu q1 (to je ta třetí závorka - to ležatý T s hvězdičkou si můžeš představit jako že automat prostě prošel nějakýma stavama než přijmul řetězec x, ta hvězdička znamená, že těch stavů mohlo být libovolně mnoho ale taky 0).
Teď to důležitý: Si ve stavu q1 a přijímáš řetězec y. Ten automat ho přijme ale všimni si, že po tom co přijmul ten podřetězec y zůstal ve stavu q1!!!!
Nakonec přijme zbytek a dostane se do koncového stavu qF.

K čemu tohle všechno? Pointa je v tom, že v tom automatu musí být nějaký cyklus. Protože máš třeba nějakou abecedu, dejme tomu {a,b} a nad ní nějakej regulární výraz, kterej ti generuje nějakej jazyk. Ten jazyk může být někonečnej, to ale znamená, že se ty řetězce toho jazyka budou postupně natahovat (proto sem taky psal aby sis představil, že je řetězec w dostatečně dlouhej). V těch řetězcích toho jazyka prostě postupně uvidíš něco co se opakuje, nějakej cyklus. Ten musíš najít taky v tom konečnym automatu.

Takže moje rada:
Převeď ten regulární výraz na DKA (jelikož je to regulární výraz tak když to budeš převádět tak ti z toho vyleze vždycky DKA takže se nemuíš bát toho, že by byl nedeterministickej). V tom automatu musíš identifikovat ten cyklus (hádám, že tohle je ten triviální způsob co myslel), začátek a konec (kde ten začátek a konec tam být nemusí).

Řek bych že když mu to takhle podáš tak bude happy...

↑ Kondr:
No tak když psal, že se to má zjistit jednoduchým podíváním se na automaty tak myšlenka byla taková, že si ten automat jakoby rozsekneš na 3 části, začátek, cyklus a konec a ty už postupně porovnáš, ano = sou stejny ne = nejsou stejný. Neni to teda nic algoritmicky přesnýho, ale odpovídá to myšlence rychlího se podívání na automaty :)
Jinak sem se mrknul na ty skripta co si doporučoval a vypadá to zajímavě no :) Takže asi pro variantu kdy chce fakt porovnávat dva DKA doporučim taky to tvoje řešení...

↑ xxsawer:Tak teď už můžu říct, že je tvůj postup špatně. Jednak tam těch cyklů může být spousta, druhak délka cyklu nemusí být v obou strojích stejná (třeba stroj, který rozppoznává jazyk slov sudé délky může mít cyklus délky 2, 4,6, ... podle toho, jak je optimálně zkonstruovaný. Zkrátka bez optimalizace nelze porovnávat automaty podle "tvaru", je potřeba do porovnání nějak zakomponovat významy jjednotlivých stavů.