# [Zk]31.5.2006 <{ForumPost(poster="gASK", timestamp=2006-05-31 10:40:51)}> Zdravím. Dostal jsem verzi, která tu koluje od první písemky. Lehce jsem si s ní poradil i přes drobné odchylky a trochu tak zaskočil Bartáka, když jsem odevzdal bezmála o hodinu dříve :twisted: Pokud si přečtete tak dvakrát slajdy, chodili jste na cvičení a projdete si ty písemky, co tu visí, musíte to dát. Jinak mi říkal, že výsledky neví kdy budou, neboť jede na týden někam pryč - ale rád by to stihnul do příští písemky. :wink: Tedy do 14.6. <{/ForumPost}> <{ForumPost(poster="SOLaris", timestamp=2006-05-31 12:35:07)}> Tak jsem byl podruhe na pisemce z Automatu. Pokud pujdete jako na opravny pokus jako ja, tak se vas zepta jakou jste psali variantu a pak vam da tu kterou jste nepsali. Takze na potreti uz vite co bude v pisemce ;) . Jinak jsem zachytil otazky skupiny A: 01)Formalni generatvini gramatika 02)Tvar pravidel BKG 03)prechodova fce ZA - def. obor a obor hodnot 04)L*={w... 05)neco s minimalnim KA(ve tride ekvivalentnich automatu ma nejmensi pocet stavu). definovat 06)L1(L2 U L3)=L1L2 U L1L3 dokazat 07)KA X={a,b} L(a)={w| pocet b je delitelny 2 i 3(takze 6)} 08 ) 1^k1^l0^k - zda je regularni. 09)Napsat nejakou BKG, u ktere kdyz nejprve vyhodite nedosazitelne neterminaly a pote odstranite neterminaly negenerujici slovo tak nedostanete redukovanou gramatiku. Potom jeste formalne napsat co je redukovana gramatika 10)dukaz pumping lemma 11)sestrojit TS X={a,b} L(TS)={w| |w|=2k}. co to je za jazyk v Chomskeho usporadani 12)zadan derivacni strom. vypsat pravidla pouzita v tomto stromu a napsat levou derivaci 13)KA -> regularni vyraz. KA: __________________ | | a | b | ------------------ -> | 1 | 2 | 3 | ------------------ <- | 2 | 2 | 2 | ------------------ | 3 | 2 | 2 | ------------------ 14)G1 : S->aSb|A, S->aA|lambda G2: S->aSb|B, B->Bb|lambda. Formalne napsat co G1a G2 generuji a jak vypada jejich prunik 15)Ekvivalence dvou automatu. stacilo u prvniho vyskrtat nedosazitelne stavy a potom znormalizovat. Snad uz potreti nebudu muset jit... :) <{/ForumPost}> <{ForumPost(poster="twoflower", timestamp=2006-05-31 13:17:37)}> > gASK wrote: > Lehce jsem si s ní poradil i přes drobné odchylky a trochu tak zaskočil Bartáka, když jsem odevzdal bezmála o hodinu dříve :twisted: Sakris, neblaznete lidi, jeste zacne vymyslet nove varianty, kdyz se bude odevzdavat o hodinu driv :-) <{/ForumPost}> <{ForumPost(poster="macbeth", timestamp=2006-05-31 13:53:52)}> Potvrdzujem, ze pisomka je celkom v pohode, hadam to dam... Bol som prvy raz a tiez som dostal variant A, presne to, co je tu popisane vyssie... Myslel som, ze to bude tazsie, resp ze sa bude striedat viac variantov pisomiek, no ale nestazujem sa :) Conclusion: preberte si tie tri pisomky a mate to vo vacku... az na to, ze v 10.) urcite nebol dokaz pumping lemmy!!! bolo tam dokazat alebo vyvratit tvrdenie: L regularny => existuje p take, ze pre kazde |z|>=p existuju u, v a w take, ze **|w| <= p**, v != lambda a pre kazde i plati uv^iw patri do L. teda oproti pumping lemme, kde |uv| <= p je to trosku rozdiel, i guess <{/ForumPost}> <{ForumPost(poster="macbeth", timestamp=2006-06-05 10:14:32)}> Tak uz su vysledky... sice tesne, ale dal som... :roll: <{/ForumPost}> <{ForumPost(poster="gASK", timestamp=2006-06-05 10:27:24)}> :twisted: Mám to. Ostatně všichni to mají, až na dva nešťastné - asi se málo koukali na fórko :wink: Kdy a kde se to dá nechat zapsat do indexu? <{/ForumPost}> <{ForumPost(poster="macbeth", timestamp=2006-06-05 10:29:37)}> > gASK wrote: > Kdy a kde se to dá nechat zapsat do indexu? > [http://kti.mff.cuni.cz/~bartak/automaty/zkousky.html](http://kti.mff.cuni.cz/~bartak/automaty/zkousky.html) wrote: > Výsledky zkoušek budou zapisovány do indexů v den zkoušek po písemkách, tj. v cca 11:00 (v S5), případně v úterý 13.6.2006 ve 13:00 - 14:00 v pracovně přednášejícího (případně jindy po předchozí domluvě). <{/ForumPost}> <{ForumPost(poster="Dawe", timestamp=2006-06-12 22:17:06)}> > macbeth wrote: > > L regularny => existuje p take, ze pre kazde |z|>=p existuju u, v a w take, ze **|w| <= p**, v != lambda a pre kazde i plati uv^iw patri do L. Můžu se zeptat, jestli tohle někdo řešil? Já jsem došel k tomu, že kdybych vzal 1 0^n a položil p=n, pak by mělo jít pumpovat 1, ale ta nejde ač je to regulární jazyk. Což mi dává spor a tvrzení neplatí. Jestli to mám blbě, opravte mě prosím, dík. <{/ForumPost}> <{ForumPost(poster="Tuetschek", timestamp=2006-06-12 22:38:11)}> Ja bych hadal ze to tvrzeni plati, kdyz plati i pumping lemma, ktery je vlastne to samy jeste s jednou podminkou navic (ale krk za to nedam) :roll: <{/ForumPost}> <{ForumPost(poster="macbeth", timestamp=2006-06-13 08:44:14)}> > Dawe wrote: > Můžu se zeptat, jestli tohle někdo řešil? Já jsem došel k tomu, že kdybych vzal 1 0^n a položil p=n, pak by mělo jít pumpovat 1, ale ta nejde ač je to regulární jazyk. Což mi dává spor a tvrzení neplatí. Jestli to mám blbě, opravte mě prosím, dík. Neviem, ja som na to isiel tak, ze ked si vezmem slovo z dlzky napr 3p, potom ak |w| <{ForumPost(poster="Dawe", timestamp=2006-06-13 12:48:40)}> To si nemyslím, že je korektní řešení, protože přeci nemusíš použít to stejný "p" pro tohle lemma a pro pumping lemma. Je řečeno že nějaký takový "p" existuje, ale ne že je nějak daný. <{/ForumPost}> <{ForumPost(poster="macbeth", timestamp=2006-06-13 13:12:20)}> Hm...neviem, asi mas pravdu... <{/ForumPost}> <{ForumPost(poster="Che", timestamp=2006-06-14 11:19:45)}> > macbeth wrote: > L regularny => existuje p take, ze pre kazde |z|>=p existuju u, v a w take, ze **|w| <= p**, v != lambda a pre kazde i plati uv^iw patri do L. Já jsem to zkusil přes důkaz podobný tomu u pumping lemma s jediným rozdílem: **místo prvního stavu, který projdeme dvakrát, zvolíme poslední takový stav**. Pak výpočet pro část slova od tohoto stavu mohl použít maximálně p-1 stavů, tedy dokonce platí |**w**| < p. 8) Opravte mně, pokud se mýlím (nejlíp ještě dneska - zítra jdu na zkoušku :) ) <{/ForumPost}>