Zkouška 11.6.08

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
Flavius Vespasianus

Zkouška 11.6.08

Příspěvek od Flavius Vespasianus »

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...
Xerxes
Matfyz(ák|ačka) level I
Příspěvky: 37
Registrován: 23. 1. 2007 16:32
Typ studia: Informatika Bc.
Bydliště: Zlínský kraj / Kolej 17. listopadu
Kontaktovat uživatele:

Re: Zkouška 11.6.08

Příspěvek od Xerxes »

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...
lj8
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 3. 6. 2007 18:23
Typ studia: Kombinace Informatika - Matematika

Re: Zkouška 11.6.08

Příspěvek od lj8 »

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 :?
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: Zkouška 11.6.08

Příspěvek od peterblack »

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
kr4UT1k
Matfyz(ák|ačka) level II
Příspěvky: 55
Registrován: 29. 6. 2007 22:00
Typ studia: Informatika Mgr.
Bydliště: Praha 6 - Střešovice

Re: Zkouška 11.6.08

Příspěvek od kr4UT1k »

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)}
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: Zkouška 11.6.08

Příspěvek od peterblack »

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
kr4UT1k
Matfyz(ák|ačka) level II
Příspěvky: 55
Registrován: 29. 6. 2007 22:00
Typ studia: Informatika Mgr.
Bydliště: Praha 6 - Střešovice

Re: Zkouška 11.6.08

Příspěvek od kr4UT1k »

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
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: Zkouška 11.6.08

Příspěvek od peterblack »

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 5998 x
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Re: Zkouška 11.6.08

Příspěvek od lickra »

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.
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: Zkouška 11.6.08

Příspěvek od peterblack »

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,λ)	
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Re: Zkouška 11.6.08

Příspěvek od lickra »

Jo tak sem to myslel.
Ono to c je tam jenom zarazka.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“