[Zk]31.5.2006

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.

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

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 :-)

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

Tak uz su vysledky...
sice tesne, ale dal som... :roll:

: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?

gASK wrote: Kdy a kde se to dá nechat zapsat do indexu?

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

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.

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:

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|<p, tak |uv| musi byt nutne vacsia ako p, cize neplati pumping lamma a kedze p.l. je nutna podmienka, tak jazyk nie je regularny.

Ale neviem, vzhladom na moj vysledok na pisomke by som sa na toto riesenie radsej nespoliehal... :roll:

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

Hm...neviem, asi mas pravdu...

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 :) )