Datum a cas: 2-MAY-1997 13:45 Vec: Skuska z fojakov Cafte bratia informatici, nas oblubeny prednasajuci je uz aj nasim oblubenym skusajucim. Najma pre mna, lebo som prave u neho urobil skusku. Chcete vediet, ako to prebiehalo? Ak nie, mozete tento mail zmazat, lebo nic ine sa tu nepise. Teda, dal nam kazdemu dve otazky, nechal asi polhodinu / tristvrtehodinu na premyslenie, potom sa prisiel podivat, ako daleko sme pokrocili, vyslovil namety na dalsiu cinnost a nechal nas pracovat dalej, a tak sa to periodicky opakovalo. (Zvladol som to na dve periody.) A ake boli otazky? Ja som mal tieto: 1. definujte nedeterministicky dvojsmerny konecny automat s end-markerami a urcite jeho silu, 2. povedzte v zavislosti od f nieco o uzavretosti triedy NSPACE(f(n)) na _komplement_. (To je trieda rozpoznavana nedeterministickymi turingacmi, ktore pouzivaju pri vstupe dlzky n najviac f(n) policok, ale to mi uz Rovan nepovedal - treba vediet.) Palenicove otazky (prave teraz nad nimi pracuje): 1, definujte 0L Lindenmayerove systemy, teda take "gramatiky", ktore pracuju nad nejakou abecedou (nerozoznavaju sa terminalne a neterminalne symboly), pre kazde pismeno existuje aspon jedno prepisovacie pravidlo, pravidla su bezkontextove, tj. su z mnoziny A x A* (kde A je abeceda, x je karteziansky sucin), namiesto "pociatocneho neterminalu" (sigmy) mame "pociatocne slovo" a (pozor!) krok odvodenia vyzera tak, ze na kazde pismeno v slove aplikujeme odvodzovacie pravidlo (v jednom kroku, paralelne). Do jazyka tejto gramatiky potom patria vsetky slova, ktore takto vygenerujeme. Okrem definicie ma zistit aj nieco o uzaverovych vlastnostiach. 2. Linearne bezkontextove gramatiky su take, ktorych pravidla su z mnoziny N x (T* N T* zjednotenie T*) (teda na pravej strane max. 1 neterminal). Treba zistit, ci je rozhodnutelna prazdnost ich prieniku a ci su uzavrete na zretaznenie. Ako vidite, Palenica ma trochu zaujimavejsie priklady ako ja (som za to trochu urazeny, ale naozaj len trochu :-). Priklady ostatnych si uz presne nepamatam a nepresne nechcem nic pisat, ved napokon nech o tom napisu zase oni. Celkovy dojem zo skusky: Rovan ma celkom humanisticko-vedecky pristup k svojim obetiam, takze clovek aj ked nieco domota, ma slusnu sancu sa z toho vysomarit (aj ked mne vynadal, zevraj mam neusporiadany prejav s nadychom stredoskolskeho humoru :-))). Lide, mjel sem vas rad, bdete, a keby ste nieco odomna xceli, zamailujte, Kaktus. Datum a cas: 12-MAY-1997 14:30 Vec: FoJa Cao Ziaci ... Akosi som zabudol napisat priklady z fojakov ... Moje boli taketo : 1. Definuj novy stroj, ktory je zhodny s NZA a ma jednu specialnu instrukciu pre homomorfizmus zasobnika. Tento homomorfizmus je dopredu dany, pricom zobrazuje kazdy znak zasobiku na prave jeden znak zasobnikovej abecedy. Urci silu tohto stroja. Ja napisem aspon odpoved, su rovnako silne ... Ak chce niekto dokaz, moze ma kontaktovat ... 2. Je trieda DTIME(n^2) uzavreta na prienik? Ano, je. Dokaz je podobny tomu z pisomky ... Este jedna vec, Rovan sa nepriamo vyjadril, ze neskorsie skusky budu lahsie ... siR Datum a cas: 13-MAY-1997 11:04 Vec: RE: FoJa > tauso, > jednym zo zakladnyx cielov tejto skoly je naucit ta vyjadrovat sa tak > aby ti ostatni rozumeli > tak sa pozna matik od sp > (rozumej sarlatanskeho pavedca) > > a teda > ja vobec nerozumiem, co robi ta "specialna instrukcia pre homomorfizmus" > (asi bude nejako definovana tym homomorfizmom, ale ako...) > > a kedy sa spusta > atd > ale pretoze ma to zaujima > mohol by si mi to vysvetlit > dik kaktus Spusta sa to normalne pre nejake hodnoty delta funkcie a zhomomorfizuje to cely zasobnik naraz. siR Datum a cas: 14-MAY-1997 12:32 Vec: FoJa Cafte vsetci, Prave som vysiel z miestnosti M213, kde sa konala skuska z FoJa. Ujo Rovan bol velmi mily, dal nam tolko casu, kolko sme chceli (mozno aj preto, ze sme boli iba dvaja). Ulohy sme mali kazdy dve. Obtiaznost uloh sa pre kazdeho cloveka urci samostatne podla jeho vysledkov z pisomiek (ak ste mali vela bodov, tak budu zadania znacne tazsie ako ked ste presli len o chlp). Ja som mal zadanie velmi lahke, pretoze som prechadzal cez pisomky len o ten chlp. Tu su: 1. Ukazte, ze L_CF = L_PDA. 2. Trieda rekurzivnych jazykov a uzavretosti na rozne operacie. ad 1. Bolo treba urobit obe konstrukcie z prednasky, a dokazat aspon tu, ktora hovori, ze L_CF je podmnozinou L_PDA. Konstrukcie aj dokaz bolo treba urobit formalne. ad 2. Operacii bolo treba co najviac, kazdu dokazat (slovne ale detailne). Ja som urobil komplement, zjednotenie, prieniek, zretazenie, zrkadlovy obraz, homomorfizmus, inv. hom, nevymazavajuci hom. A to stacilo. To vsetko som spravil za asi hodinku, potom sme si trochu s Rovanom o rieseniach porozpravali a bolo to. Takze vela zdaru ! Kamil Poturnaj. Datum a cas: 14-MAY-1997 12:52 Vec: Fojaky Caute ! Ja som bol tym druhym, koho Kamil spominal, a tu su moje ulohy: 1.Dokazte, ze Problem prislusnosti pre bezkontextove gramatiky je rozhodnutelny 2.Mame def. linearne bezkont.gramatiky tak, ze na pravej strane maju maximalne 1 neterminal , terminalov hocikolko ... Dokazte, ze su slabsie ako trieda obycajnych bezkontextovych a vyslovte pumpovaciu lemu pre ne ... Bye Juro. Datum a cas: 20-MAY-1997 11:45 Vec: skuska z foja Spoteny a nervovo zhruteny som prave spravil skusku z foja. Mal som tieto otazky: 1. Zadefinujte stroj, ktory bude zasobnikovy automat taky, ze ak raz vymaze zo zasobnika, uz do neho nesmie viac pridavat. Urcte silu, uzavretost, etc. 2. Uzaverove vlastnosti rekurzivnych jazykov. Good luck, Karol Ruckschloss Datum a cas: 20-MAY-1997 13:00 Vec: skuska z foja 2: judgement day caute!! len v kratkosti zreferujem moje otazky: 1. uzavretosti L_rec (plus zadefinovat triedu L_rec) 2. majme zasobnikove automaty ktore po isty stav muozu zapisovat na zasobnik a potom uz len citat...zadefinovat podrobne, porovnat s L_PDA, uzavretsoti... vela stastia! peter Datum a cas: 20-MAY-1997 13:17 Vec: foja moja cafte, aha: 1. modifikovana bezk. gram je taka, ze pri pouziti pravidla A->v aplikuje toto pravidlo na VSETKY vyskyty A v generovanom slove. Porovnat s Lcf, uzaverove vlastnosti, definovat... 2. PKP a veci s tym suvisiace dobre, nie? pla Datum a cas: 21-MAY-1997 14:41 Vec: fojaky ak vas este nestve pocet novych mailov pridavam dalsi rovan je celkom fajn a priklady dokaze tiez davat celkom slusne : 1. zadefinovat dvojpaskovy jednosmerny nedeterministicky automat ( na kazdej paske to muoze mat ine slovo ) a porovnat to s a-prekladacom 2. homomorfizmus na triedach chomskeho hierarchie ( oplati sa pozriet duokaz uzavretosti R ) to je odo mna vsetko. buducim jazykarom prajem vela stastia a uz idem do... koza Datum a cas: 29-MAY-1997 13:24 Vec: Foja vobec nie bez boja Dnesnu skusku mame za sebou, tak tu su nejake priklady: 1 namontovat do a-prekl. zasobnik, def., sila, uzavretost... 2 uzavretost Lcs 1 kazda netriv. vlastnost je nerozh. 2 PDA ma miesto zasobnika frontu; ma/nema povoleny krok na \epsilon: sila, uzavretost, def.,... 1 a-prekladac: def, uzavretost R,Lcf,Lcs,Lre na zobr. a-preklad. 2 rozsirene Lcf, to su Lcf s pravidlami pararelneho prepisu vsetkych rovnakych neternminalov (ale aj normalnymi), sila, uzav., porov. s Lcf,... 1 casova zlozitost- definovat, ako je to s konstantami? 2 zariadenie pozostavajuce z N konecnych automatov. kazdy z nich cita jedno pismeno a stav sa meni na zaklade citaneho pismena, stavu, stavu laveho a praveho suseda. Osetrit konce. Def., uzavr, porovnat. 1 Pumpovacka 2 akesi grafove gramatiky, ci co. Drzim palce. -- M a t'o www: http://kepler.fmph.uniba.sk/domany5