Predtermin 22.5.2008

Zdravim,

ako to vypadalo tentokrat? Boli by ste ochotny podelit sa o nejake tie otazky z testu? :roll:

tiez by ma potesilo keby sa niekto ozval

cast 1 - zaskrtavaci test (niektore moznosti som mozno trochu poplietol pisem to tak zhruba ako si to pamatam)

Otazky v teste boli dost podobne tym ktore tu su na fore nafotene (niektore identicke v niektorych bolo zmenene jedno slovo a nasli sa aj take otazky ktore som tu na fore este nevidel) Napriklad prva otazka bola ze L^0 je podmnozina ktoreho jazyka (otazka na http://matfyz.cskd.cz/automaty-1.jpg) Potom nasledovala otazka na pravy kvocient. Dalej si spominam ze bola otazka na doplnok rekurzivnych jazykov, ako je mozne simulovat vypocet nedeterm. TS pomocou determ. (moznosti prehladavanie do sirky, hlbky...)
Tiez tam bola otazka na vztah v nedeterministickom konecnom automate medzi mnozinou prjimacich stavov a medzi mnozinov stavov do ktorych sa da dostat z pociatocneho stavu pomocou nejakeho slova z jazyka tohto automatu. Dalej otazka na ekvivalenciu stavov (ten isty odkaz ako predchadzajuci - otazka uplne dole)

Co sa tyka otazok ktore som ja nafotene na tychto forach nezaregistroval a teda sa domnievam ze su nove. Jedna otazka bola na algoritmicky nerozhodnutelne problemy - Mali sme zasktrnut problemy ktore nie su algoritmicky riesitelne. Vsetky moznosti sa tykali bezkonteztovych gramatik a myslim ze trebalo zaskrtnut ze sa neda algoritmicky rozhodnut ci je dana bezkont. gramatika viceznacna a este nejaka moznost s prienikom bezkonteztovych jazykov.
Dalej tam bola otazka asi taka: L1 a L2 su 2 jazyky z tej istej triedy chomskeho hierarchie. Potom a) L1 prienik L2 vzdy lezi v tej istej triede. b) prienik L1 L2 moze lezat v inej triede c) prienik L1 L2 lezi v tej triede chomskeho hierarchie kde aj ich zjednotenie a este nieco po d.
Celkom vtipna sa mi zdala otazka na linearne obmedzene automaty. Na prvy pohlad mi znela trivialne. Linearne obmedzene automaty maju:
a) pasku obmedzenu na jednej strane (a este tam bola k tomu nejaka poznamka v zatvorke asi nieco o jednosmernej paske) b) pasku obmedzenu na 2 stranach c) pasku obmedzenu vstupnym slovom d) pasku obmedzenu vystupnym slovom. Odpoved b som zaskrtol hned - len som potom uvazoval ci nemam zaskrtnut aj odpoved a - a potom som rozmyslal aj o odpovediach c,d:-)

Moj nazor je taky ze ak si clovek prejde dokladne vsetky otazky nafotene na tomto fore tak by to na 19 bodov mohol s trochou stastia dat.

cast 2 - pisomka
Mal som jazyk { ww | w je prvkom {0,1}* } Mal som zaradit tento jazyk (dokazat to - je to kontextovy tak som si mohol vybrat ci vygenerujem gramatiku alebo odpovedajuci LOA ) Dalej som mal ukazat preco nepatri do nizsej triedy (pumping lemma) a tiez som mal tvrdenie ktore som pri tom dokaze pouzil dokazat (cize som mal dokazat pumping lemmu)
Myslim ze nieco podobne sa tu na fore dopodrobna rozoberalo. Hodnotenie pisomky sa mi zdalo celkom mierne - rozhodne teda nemusi byt vsetko spravne ale asi by sa clovek mal byt schopny opravit (ak chce lepsiu znamku).

Konecne nejaka slusna odpoved. :)
Dik.

rudot wrote:Linearne obmedzene automaty maju:
a) pasku obmedzenu na jednej strane (a este tam bola k tomu nejaka poznamka v zatvorke asi nieco o jednosmernej paske) b) pasku obmedzenu na 2 stranach c) pasku obmedzenu vstupnym slovom d) pasku obmedzenu vystupnym slovom. Odpoved b som zaskrtol hned - len som potom uvazoval ci nemam zaskrtnut aj odpoved a - a potom som rozmyslal aj o odpovediach c,d:-)

Zdar,

nevies nahodou ake mali byt v tejto otazke odpovede? Ja by som to videl takto:
a) nie - v zmysle "prave" jednej (zavisi od presnej formulacie.)
b) ano
c) ano (? => ma mensi vystup => d nie ?)
d) nie?

Mno tak tu si niesom isty hlavne tym d, momze mi niekto potvrdit alebo vyvratit moje domnieknky? :roll:

MIKI wrote:

rudot wrote:Linearne obmedzene automaty maju:
a) pasku obmedzenu na jednej strane (a este tam bola k tomu nejaka poznamka v zatvorke asi nieco o jednosmernej paske) b) pasku obmedzenu na 2 stranach c) pasku obmedzenu vstupnym slovom d) pasku obmedzenu vystupnym slovom. Odpoved b som zaskrtol hned - len som potom uvazoval ci nemam zaskrtnut aj odpoved a - a potom som rozmyslal aj o odpovediach c,d:-)

Zdar,

nevies nahodou ake mali byt v tejto otazke odpovede? Ja by som to videl takto:
a) nie - v zmysle "prave" jednej (zavisi od presnej formulacie.)
b) ano
c) ano (? => ma mensi vystup => d nie ?)
d) nie?

Mno tak tu si niesom isty hlavne tym d, momze mi niekto potvrdit alebo vyvratit moje domnieknky? :roll:

Správně má být pouze a jenom za c)!!! d) je nesmysl (jake vystupni slovo??), a) je nejaka podivnost, ale kazdopadne to nema s LOA nic spolecneho a b) je konecny automat

kr4UT1k wrote:Správně má být pouze a jenom za c)!!! d) je nesmysl (jake vystupni slovo??), a) je nejaka podivnost, ale kazdopadne to nema s LOA nic spolecneho a b) je konecny automat

No tak neviem - obmedzenie podla mna znamena ja to, ze nemozem ist za nejaky symbol. Pokial to bolo myslene tak, ze sa jedna iba o dlzku pasky, tak potom je jasne, ze to b) a ani a) byt nemoze.

d) je nesmysl (jake vystupni slovo??)

To sa spytaj Bartaka ;)

Prostor výpočtu je definován vstupním slovem a automat
při jeho přijímání nesmí překročit jeho délku
u monotónních (kontextových) derivací to není problém:
žádné slovo v derivaci není delší než výstupní slovo

Dik za za opravu. :)

Každopádně jsem zaškrtl jen c) a bylo to správně, ať už to bylo myšleno jakkoliv.

K tomu vstupnímu/výstupnímu slovu(to už není 100%): když mám automat, který má rozhodnout, zda slovo do jazyka patří, tak je to slovo vstupní, když mám gramatiku, která je** generuje**, pak je to slovo výstupní. A tady mám automat, takže žádné výstupní.

Tak nevim, ja mel b a nemel c a mel jsem mit obe, aby to bylo spravne...