[Zk]31.5.2006

[gASK]

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

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. Tedy do 14.6.

[SOLaris]

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:

Kód: Vybrat vše

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

[twoflower]

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

Sakris, neblaznete lidi, jeste zacne vymyslet nove varianty, kdyz se bude odevzdavat o hodinu driv

[macbeth]

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

[macbeth]

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

[gASK]

Mám to. Ostatně všichni to mají, až na dva nešťastné - asi se málo koukali na fórko

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

[macbeth]

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

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

[Dawe]

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.

[Tuetschek]

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)

[macbeth]

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

[Dawe]

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

[macbeth]

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

[Che]

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.

Opravte mně, pokud se mýlím (nejlíp ještě dneska - zítra jdu na zkoušku )