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