# Zkouška 11.6.08
<{ForumPost(poster="Flavius Vespasianus", timestamp=2008-06-11 17:20:13)}>
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...
<{/ForumPost}>
<{ForumPost(poster="Xerxes", timestamp=2008-06-11 18:36:19)}>
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...
<{/ForumPost}>
<{ForumPost(poster="lj8", timestamp=2008-06-11 19:26:52)}>
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 :?
<{/ForumPost}>
<{ForumPost(poster="peterblack", timestamp=2008-06-23 13:17:17)}>
> 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
<{/ForumPost}>
<{ForumPost(poster="kr4UT1k", timestamp=2008-06-23 13:28:46)}>
> 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)}
<{/ForumPost}>
<{ForumPost(poster="peterblack", timestamp=2008-06-23 13:36:36)}>
> 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
<{/ForumPost}>
<{ForumPost(poster="kr4UT1k", timestamp=2008-06-23 14:07:38)}>
> 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
<{/ForumPost}>
<{ForumPost(poster="peterblack", timestamp=2008-06-23 14:22:20)}>
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](/Forum%20archiv/Attachments/2690_8f47e1ec740ed5777670ad41bb471ff4)*
<{/ForumPost}>
<{ForumPost(poster="lickra", timestamp=2008-06-23 18:07:33)}>
> 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.
<{/ForumPost}>
<{ForumPost(poster="peterblack", timestamp=2008-06-23 19:10:13)}>
> 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={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
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,λ)
<{/ForumPost}>
<{ForumPost(poster="lickra", timestamp=2008-06-23 19:45:33)}>
Jo tak sem to myslel.
Ono to c je tam jenom zarazka.
<{/ForumPost}>