Zkouška 11.6.08

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

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

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

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 :?

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

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

peterblack wrote:

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

v tomhle:

peterblack wrote: (p,0,Z)={(p,AZ)}
(p, lambda,Z)={(p,lambda)}

kr4UT1k wrote:

peterblack wrote:

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

v tomhle:

peterblack wrote: (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

peterblack wrote: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

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

Attachments:

• det.png

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.

lickra wrote: 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={wcw^R| 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

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

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