Zkouška 11.6.08

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Zkouška 11.6.08

Re: Zkouška 11.6.08

od lickra » 23. 6. 2008 19:45

Jo tak sem to myslel.
Ono to c je tam jenom zarazka.

Re: Zkouška 11.6.08

od peterblack » 23. 6. 2008 19:10

lickra píše: To ze si nemuzes vybirat nestaci na definici detministickeho atuomatu, je potreba aby byli definove vsechny situace ktere mohu nastat: kombinace stav a pismeno.
Definice pro DZA:
Říkáme, že zásobníkový automat
M=(Q,X,Y,δ,q0,Z0,F), je deterministický, jestliže platí:
– ∀p∈Q, ∀a∈X∪{λ}, ∀Z∈Y |δ(p,a,Z)|≤1 //nemuzeme si vybirat
– ∀p∈Q, ∀Z∈Y ( δ(p,λ,Z)≠∅ ⇒ ∀a∈X δ(p,a,Z)=∅ ) //ukonceni vzpoctu
Každý krok výpočtu je přesně určen.
myslis vsechny situace (kombinace stav a pismeno), ktere muzou nastat aby slovo bylo prijato?

protože jinak jsem našel příklad kdy nejsou definovany vsechny kombinace stav a pismeno:
Přiklad: DZA prijimajici L={wcwR| w∈{a,b}+}.

Řešení: ukládej postupně symboly na zásobník a po přečtení středového symbolu c porovnávej vstupní symboly se symboly postupně umazávanými ze zásobníku

Kód: Vybrat vše

	M=({q0,q1,q2}, {a,b,c}, {Z,a,b}, δ, q0, Z, {q2}) 
		δ(q0,X,Y)= (qo,XZ)	pro všechna X∈{a,b} a Y∈{Z,a,b}   
		δ(q0,c,Y)= (q1,Y)	pro všechna Y∈{a,b} 
		δ(q1,X,X)= (q1,λ)	pro všechna X∈{a,b} 
		δ(q1,λ,Z)= (q2,λ)	

Re: Zkouška 11.6.08

od lickra » 23. 6. 2008 18:07

ale automat je deterministicky, prave kdyz si pri vypoctu nemuze vybirat. Ten tvuj si mohl vybrat, kdyz mel na zasobniku Z na vstupu 0, jestli ji nacte, nebo jestli provede lambda krok
To ze si nemuzes vybirat nestaci na definici detministickeho atuomatu, je potreba aby byli definove vsechny situace ktere mohu nastat: kombinace stav a pismeno.
Definice pro DZA:
Říkáme, že zásobníkový automat
M=(Q,X,Y,δ,q0,Z0,F), je deterministický, jestliže platí:
– ∀p∈Q, ∀a∈X∪{λ}, ∀Z∈Y |δ(p,a,Z)|≤1 //nemuzeme si vybirat
– ∀p∈Q, ∀Z∈Y ( δ(p,λ,Z)≠∅ ⇒ ∀a∈X δ(p,a,Z)=∅ ) //ukonceni vzpoctu
Každý krok výpočtu je přesně určen.

Re: Zkouška 11.6.08

od peterblack » 23. 6. 2008 14:22

jo sorry, ja to srovnaval se slidama
uplne nakonci tam ma Bartak taky lambda prechod a pise tam ze to neni nedeterminismus (protoze si nemuzeme vybirat)
det.png
det.png (32.01 KiB) Zobrazeno 6191 x

Re: Zkouška 11.6.08

od kr4UT1k » 23. 6. 2008 14:07

peterblack píše:jo jasne diky, chapu to tak ze u zasobnikovych automatu existuji i deterministcké lambda kroky
tohle nevim, jak jsi myslel, ale automat je deterministicky, prave kdyz si pri vypoctu nemuze vybirat. Ten tvuj si mohl vybrat, kdyz mel na zasobniku Z na vstupu 0, jestli ji nacte, nebo jestli provede lambda krok

Re: Zkouška 11.6.08

od peterblack » 23. 6. 2008 13:36

kr4UT1k píše:
peterblack píše:
ee v cem je nedeterministicky? chapu ze ten jazyk neni bezprefixovej ale proc ten muj automat je nedeterministickej
diky
v tomhle:
peterblack píše: (p,0,Z)={(p,AZ)}
(p, lambda,Z)={(p,lambda)}
jo jasne diky, chapu to tak ze u zasobnikovych automatu existuji i deterministcké lambda kroky

Re: Zkouška 11.6.08

od kr4UT1k » 23. 6. 2008 13:28

peterblack píše:
ee v cem je nedeterministicky? chapu ze ten jazyk neni bezprefixovej ale proc ten muj automat je nedeterministickej
diky
v tomhle:
peterblack píše: (p,0,Z)={(p,AZ)}
(p, lambda,Z)={(p,lambda)}

Re: Zkouška 11.6.08

od peterblack » 23. 6. 2008 13:17

Xerxes píše:Příklad jsem měl zhruba takový:

Kód: Vybrat vše

Sestrojte zásobníkový automat, který prázdným zásobníkem přijímá jazyk všech správných uzávorkování nad abecedou {0, 1} (0 je otevírací závorka a 1 uzavírací). Lze udělat deterministicky? Definujte nedeterministický a deterministický zásobníkový automat a způsoby přijímaní slov a dokažte vztahy mezi jazyky, které generují.
prazdnym zasobnikem:
(p,0,Z)={(p,AZ)}
(p,0,A)={(p,AA)}
(p,1,A)={(p,lambda)}
(p, lambda,Z)={(p,lambda)}

ee v cem je nedeterministicky? chapu ze ten jazyk neni bezprefixovej ale proc ten muj automat je nedeterministickej
diky

Re: Zkouška 11.6.08

od lj8 » 11. 6. 2008 19:26

Mozna to nekomu pomuze, seznam par veci, co mi v testu prislo nove oproti minulym:
- neco, jestli je F konecna mnozina u determ. K automatu (tak nejak)
- kanonicky TS prijima prave stejne a) jako TS b) TS s jednou zarazkou...
- kdyz ND automat ma n stavu, pak D automat ma maximalne 2 na n stavu, n na n stavu (2 na n, protoze to jsou moznosti potencni mnoziny, n na n se zaskrtne, protoze to je vetsi cislo nez 2 na n)
- neco s poctem stavu u D automatu (asi jako do kazdyho stavu vede hrana (ne, musel by byt redukovany), do kazdyho stavu vede maximalne tolik hran, kolik je stavu, myslim, ze z toho nebyla pravda nic, ale jisty si nejsem).

Pak tam bylo typicky:
- spoji se dve BK gramatiky G1 do G2 do G a ze se to rovna zretezeni (! - u K gramatiky to zvladne vygenerovat vic)
- zase pozor, ze L+ != L* \ {lambda}...
- kdyz je DZA koncovym stavem, tak z toho vyplyne bezkontextovost a vsechno nad ni, naopak regularni a DZA prazdnym zasobnikem ne nutne (muzou byt, ale ne vzdy, nezaskrtava se)
- novy D automat, ktery ma prijima Q-F -> X* - L(A) (kdyby byl ND, tak to neni pravda
- isomorfismy/homomorfismy/ekvivalence reduktu
- q0 je pocatecni stav DKA, w je z F -> w je prijimaci, w je doszitelny...
- zase nejaky DKA s neprazdnym slovem -> existuje slovo w z X*, ze rozsirena prechodova funkce (q0, w) bude z F, existuje slovo taky z L(A) a plati to pro kazdy w z L(A) (a neplati pro kazdy w z X)

Jestli si jeste na neco vzpomenu, tak to sem dopisu, jinak taky treba dopiste, uz tu dlouho nebylo nic uzitecneho k tomu testu, ktery je asi nejvetsi problem :?

Re: Zkouška 11.6.08

od Xerxes » 11. 6. 2008 18:36

Jo, když na začátku říkal, že se v testu ptá na věci, co zazněly na přednášce, ale nebyly ve slidech, docela mi zatrnulo, protože jsem pět přednášek vynechal a ani na těch, co jsem absolvoval, jsem si toho navíc moc nepoznamenal.

Nicméně když člověk problematiku trochu zná, dá se většina odpovědí vymyslet. Test jsem odevzdával jako jeden z posledních až něco přes hodinu od začátku a někde jsem i docela hádal. Výsledek 28 z 29 mi docela vyrazil dech...

Příklad jsem měl zhruba takový:

Kód: Vybrat vše

Sestrojte zásobníkový automat, který prázdným zásobníkem přijímá jazyk všech správných uzávorkování nad abecedou {0, 1} (0 je otevírací závorka a 1 uzavírací). Lze udělat deterministicky? Definujte nedeterministický a deterministický zásobníkový automat a způsoby přijímaní slov a dokažte vztahy mezi jazyky, které generují.
Napsal jsem mu ten automat (ten je docela jednoduchý) a že nejde udělat dereministicky, pokud má přijímat prázdným zásobníkem (protože jazyk není bezprefixový), ale koncovým stavem by to deterministicky šlo a jak (už jenom princip). Pak jsem mu sepsal ty definice a důkaz jsem napsal jenom pro to, že přijímání koncovým stavem a prázdným zásobníkem je rovnocenné z hlediska síly automatu (oba směry).

Když si mě bral na ústní, říkal, že mít z testu o ten bod víc, tak mě pošle domů ihned. Potom velmi rychle proletěl můj výtvor a nakonec se jen zeptal, proč se musí vyztužit zásobník speciálním symbolem u převodu koncový stav -> prázdný zásobník (protože původní automat mohl po přečtení slova vyprázdnit zásobník a nebýt přitom v koncovém stavu, takže nový by bez výztuhy mohl přijímat něco navíc).

Jinak můj dojem z poslouchání toho, jak zkoušel pár lidí přede mnou, je spíš takový, že se docela hodně snaží vytáhnout z lidí něco, co by mu umožilo hodnotit je lépe. Takže největší problém je test...

Zkouška 11.6.08

od Flavius Vespasianus » 11. 6. 2008 17:20

Testové otázky byly poměrně klasické, dost možná ty samé, co včera, podle toho, co jsem slyšel.

Myslím, že ani příklady nebyly nijak neklasické, já jsem měl napsat gramatiku a^i b^j c^k i <= j <= k, dokázat že není bezkontextová a napsat definice monotonní a kontextové gramatiky a jaký je mezi nimi vztah (a dokázat ho).
Jelikož číst neumím, tak jsem tam nepsal o tom vztahu, tak mi to dal napsat - napsal jsem to skoro dobře, ale z blbé strany tam přepisoval ta pravidla ze separované na kontextovou, ale říkal jsem, že vím, že tam někde měl být nějaký problém, ale nevím, ze které strany to musím psát a proč, tak mě nad tím ještě nechal zamyslet - pořádně jsem to nevymyslel, ale stejně mi nakonec dal jedničku (z testu jsem měl 20 bodů).

Mezi písemkou a zkoušením byl libovolný čas, kdo chtěl, mohl přijít třeba za dvě nebo tři hodiny, lidí nadšených na zkoušku tam bylo dost a s každým strávil tak pět až deset minut (většinou opakovaně).
Myslím, že hodnocení je docela mírné, pokud člověk měl 17-19 bodů, tak se rozhodoval mezi 2 a 3, pokud více, tak 1 - 2. Nevím o tom, že by někoho vyhodil, i když, co jsem slyšel, někteří pořádně ani nezformulovali pumping lemma. Samozřejmě, test byl smrtelný klasicky pro tu půlku, někteří se prý snažili co nejvíce přiblížit nule...

Nahoru