Boli ste tam niekto? Pripadne by ste sa mohli podelit o zadania niektorych otazok z toho noveho testu?
Dik.
Po 25.6.2007
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 10. 12. 2004 22:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Po 25.6.2007
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
Automaty a Gramatiky
No, bol tam prakticky rovnaky test, ktory bol myslim 18. 6. - tu je link:
http://www.oskee.wz.cz/stranka/oskee.php?id=1182796373
No, to ohladom testu, co sa tyka prikladu, tak bolo potrebne vytvorit gramatiku generujucu jazyk {a<sup>i</sup>b<sup>j</sup>c<sup>k</sup> | i>j>k} - je to v slidoch a dokazat, ze je to kontextovy jazyk (napriklad cez pumping lemma). Dalej zadefinovat monotonne a kontextove gramatiky, definovat ich vstah a aj si to pekne po sebe dokazat. Nic co by bolo extremne zlozite, ale Bartak chce veci strasne exaktne, takze napriklad ked som v definicii kontextovej gramatiky dal namiesto + iterator *, tak mi to dal za 0. Inu, s panom docentom sa uvidim zase zajtra.
http://www.oskee.wz.cz/stranka/oskee.php?id=1182796373
No, to ohladom testu, co sa tyka prikladu, tak bolo potrebne vytvorit gramatiku generujucu jazyk {a<sup>i</sup>b<sup>j</sup>c<sup>k</sup> | i>j>k} - je to v slidoch a dokazat, ze je to kontextovy jazyk (napriklad cez pumping lemma). Dalej zadefinovat monotonne a kontextove gramatiky, definovat ich vstah a aj si to pekne po sebe dokazat. Nic co by bolo extremne zlozite, ale Bartak chce veci strasne exaktne, takze napriklad ked som v definicii kontextovej gramatiky dal namiesto + iterator *, tak mi to dal za 0. Inu, s panom docentom sa uvidim zase zajtra.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 49
- Registrován: 2. 2. 2006 15:58
Jo, byl to presne ten sami test.
Jako priklad jsem mel vyraz ((ab+c)<sup>+</sup> a(bc)* +b)* prevest na konecny automat (pomoci nejakeho obecneho algoritmu, ktery k tomuto postupu pujde vzdy vyuzit), moze byt u nedterministicky. Pismenka mozna uplne nesedi, ale jina to bylo asi takhle. A druha cast asi vsude stejna zni, ze mate uvest a dokaz vse, co je potreba aby to co jste udelali v prvni casti vzdycky platilo.
Zde tedy slo o Kleenovu vetu a dokazt ji. Mam dojem ze na slajdech je dukaz RV na KA neco jako ze je zrejmy, ale pome to chtel rozpitvat a treba dokazat, ze regularni jazyky jsou uzavrene na operace iterace, retezeni tad...
coz sem rekl ze ne ) tak po dalsich debatach me dal zatri.
K tomu testu, co si asi pamatuju:
3) a,c
5) mam dojem ze vse, ale jsity si tim uplne nejsem
6) a,b
7) zadani je definice dosazitelneho stavu, coz je varianta nevím ktera, nevidím tam ale je to ze existuje aspon jedno slovo z X* (pozor, ne z L) takove ze ta prechodova funkce z q1 pres to slovo se = P kde P (jde o jeden stav, takze je tam rovna se a za P si dosadte ten stav ze zadani, nevim zda je oznacen P, q, p ci jinak) je ten stav, o kterem se mluvi v zadani a zjistuje se kdy je dosazitelny.
8 ) kdy jsou dva stavy ekvivalentni, reseni je a), neni to ta varianta s w z L, protoze slovo nemusi byt z jazyka a presto ho automat precte a dostane se do stavu treba neprijimaciho, ale ten ma take ekvivalentni stav, idkyz neni prijimaci. Proto to plati pro vsechna mozna slova z X*
9) neznam reseni, nicmene odpoved JEN a) neni spravna
10) nevim jak sem mel spravne, ale myslim ze by melo jit o doplnek tedy b), DKA se prohozenim koncovych a nekoncovych stavu udela doplnek (neplati pro nedeterministicky KA).
11) reseni je b,d), chytak je v tom, ze precteni slova neznamena jeho prijeti, takze automat jen tuhle sekvenci baab zpracuje nehlede na stav kam se dostane. staci se kouknout kam se da dostat na B ktere je posledni a zda se do nich da dostat pres sekvenci baab
12) tak tady nevim vubec, zaskrtal jsem vse, ale netusim vubec
13) reseni b), je to jen jazyk L2, je to videt z koncovych stavu Q1xF2 je to sice kartezsky soucin tech stavu, ale vzdy je tam pouze stavy z F2 takze to prijima vsechny slova z A2 a nic vic. Muze to prijimat i nektera slova z A1, ale to jen kdyz jsou i v A2.
14) tady je resenim vsechny moznosti, to vim
15) netusim, daval jsem b), zasobnikovy neni nema zasobnikovou abecedu a je nedeterministicky podle te prechodove funkce.
16) b) ted uz nevim, bcko urcite plati, acko je spatne, jen mam dojem ze sem omylem zaskrtl i acko v testu
17) netusim, ze zvyku jsem zaskrtl c) )
18 ) take nevim, jen mam dojem ze odpoved jen d) byla spatne
19) a,b
20) d) jde u vrcholy uvnitr stromu, ne listy
21) nic
22) nevim jak sem to mel spravne, ale zaskrtal sem vse. BezPref jazyk se rozpoznava mam dojem prazdnym zasobnikem deterministickeho automatu, je to podmnozina jazyku ktere se rozpoznavaji det. s konecnym stavem. A protoze determinismus je slabsi nez nedeterminismus tak by pak meli platit i ty dva nedeterministicke varianty?
23) c)
24) b)
25) a,c)
26) c)
27) jen a) je spatne, mam dojem ze spravne je a,b)
28 ) ve slajdech se rika ze to znamena, ze se neda algoritmicky rozhodnout pro dany TS a jeho komfiguraci, zda bude jeho vypocet konecny. Na kterou z tech odpovedi to naroubovat si nejsem uplne jisty, rekl bych ze ta posledni?
29) b)
Jako priklad jsem mel vyraz ((ab+c)<sup>+</sup> a(bc)* +b)* prevest na konecny automat (pomoci nejakeho obecneho algoritmu, ktery k tomuto postupu pujde vzdy vyuzit), moze byt u nedterministicky. Pismenka mozna uplne nesedi, ale jina to bylo asi takhle. A druha cast asi vsude stejna zni, ze mate uvest a dokaz vse, co je potreba aby to co jste udelali v prvni casti vzdycky platilo.
Zde tedy slo o Kleenovu vetu a dokazt ji. Mam dojem ze na slajdech je dukaz RV na KA neco jako ze je zrejmy, ale pome to chtel rozpitvat a treba dokazat, ze regularni jazyky jsou uzavrene na operace iterace, retezeni tad...
coz sem rekl ze ne ) tak po dalsich debatach me dal zatri.
K tomu testu, co si asi pamatuju:
3) a,c
5) mam dojem ze vse, ale jsity si tim uplne nejsem
6) a,b
7) zadani je definice dosazitelneho stavu, coz je varianta nevím ktera, nevidím tam ale je to ze existuje aspon jedno slovo z X* (pozor, ne z L) takove ze ta prechodova funkce z q1 pres to slovo se = P kde P (jde o jeden stav, takze je tam rovna se a za P si dosadte ten stav ze zadani, nevim zda je oznacen P, q, p ci jinak) je ten stav, o kterem se mluvi v zadani a zjistuje se kdy je dosazitelny.
8 ) kdy jsou dva stavy ekvivalentni, reseni je a), neni to ta varianta s w z L, protoze slovo nemusi byt z jazyka a presto ho automat precte a dostane se do stavu treba neprijimaciho, ale ten ma take ekvivalentni stav, idkyz neni prijimaci. Proto to plati pro vsechna mozna slova z X*
9) neznam reseni, nicmene odpoved JEN a) neni spravna
10) nevim jak sem mel spravne, ale myslim ze by melo jit o doplnek tedy b), DKA se prohozenim koncovych a nekoncovych stavu udela doplnek (neplati pro nedeterministicky KA).
11) reseni je b,d), chytak je v tom, ze precteni slova neznamena jeho prijeti, takze automat jen tuhle sekvenci baab zpracuje nehlede na stav kam se dostane. staci se kouknout kam se da dostat na B ktere je posledni a zda se do nich da dostat pres sekvenci baab
12) tak tady nevim vubec, zaskrtal jsem vse, ale netusim vubec
13) reseni b), je to jen jazyk L2, je to videt z koncovych stavu Q1xF2 je to sice kartezsky soucin tech stavu, ale vzdy je tam pouze stavy z F2 takze to prijima vsechny slova z A2 a nic vic. Muze to prijimat i nektera slova z A1, ale to jen kdyz jsou i v A2.
14) tady je resenim vsechny moznosti, to vim
15) netusim, daval jsem b), zasobnikovy neni nema zasobnikovou abecedu a je nedeterministicky podle te prechodove funkce.
16) b) ted uz nevim, bcko urcite plati, acko je spatne, jen mam dojem ze sem omylem zaskrtl i acko v testu
17) netusim, ze zvyku jsem zaskrtl c) )
18 ) take nevim, jen mam dojem ze odpoved jen d) byla spatne
19) a,b
20) d) jde u vrcholy uvnitr stromu, ne listy
21) nic
22) nevim jak sem to mel spravne, ale zaskrtal sem vse. BezPref jazyk se rozpoznava mam dojem prazdnym zasobnikem deterministickeho automatu, je to podmnozina jazyku ktere se rozpoznavaji det. s konecnym stavem. A protoze determinismus je slabsi nez nedeterminismus tak by pak meli platit i ty dva nedeterministicke varianty?
23) c)
24) b)
25) a,c)
26) c)
27) jen a) je spatne, mam dojem ze spravne je a,b)
28 ) ve slajdech se rika ze to znamena, ze se neda algoritmicky rozhodnout pro dany TS a jeho komfiguraci, zda bude jeho vypocet konecny. Na kterou z tech odpovedi to naroubovat si nejsem uplne jisty, rekl bych ze ta posledni?
29) b)