Zkouska 3.6.2008

Dost otresnej zazitek...

Docela jsem ty skripta mel nabouchany, taky jsem si vypsal vsechny otazky co kdy padly a videl jsem je tady na foru nebo na nafocenych starych pisemkach.

Presto me polovina otazek totalne dostala. Bud definice a prislusne vety ve slajdech vubec nebyly (co je kanonicky TS, jak funguje automat s dvema zasobnikama, jak funguji spocetne pruniky, sjednoceni a spol., jak funguji nadmnoziny - podmnoziny ruznych kontextovych jazyku a jazyku typu 0, atd...), nebo nevim... Vysledek 17 bodu, rekl mi, ze pokud mam zajem se na to jeste podivat, tak at prijdu az to odevzdaji vsichni. Tak jsem prisel a on mi rekl, ze teda jeste mi da sanci, ze nema pomalu koho zkouset.

Dostal jsem napsat redukovany automat na abecede {a,b}, ktery konci na minimalne dva symboly a predchazejici symbolem b. Definovat ekvivalenci stavu, redukovany automat a dokazat vety, ktere mi umoznuji provest redukci a odstranit ekvivalentni stavy.

To jsem udelal, krom toho, ze jsem nedotahl jeden z hromady dukazu te druhe casti... on rekl, ze to v kombinaci s 17 body neni lepsi nez na 3 a at mu napisu Chomskeho hierarchii, definuji automaty a prislusne gramatiky a nakreslim vztahy mezi automaty a gramatikami. To jsem udelal, podival se na to, rikal, ze na dvojku to asi nebude, jeste bylo videt, ze mi ji chce dat, ale ja uz na to nemel silu a vzal za 3. Jeste jsem mu rekl, ze trojka neni nic moc a ze bych rad neco lepsiho a on ze mi to nebude psat do sisu a pokud jeste prijdu, tak si to muzu opravit.

Nakonci jeste potvrdil, ze v zari URCITE nebudou ZADNE terminy.

Jo a se mnou bojoval jeste clovek, ktery mel test na 28 nebo 27 bodu, ale pak se zamotal do nejakych definic prazdnych slov a jazyku L^0 a nakonec z neho vylezlo, ze bude rad, kdyz projde. Nevim, co pak dostal za znamku.

No tos me moc nepotesil...ja jdu zejtra a tohle sem slyset presne nechtel :twisted:

...nahodou si nepamatujes nejaky konkretni otazky z testu(a pripadne odpovedi k nim)?

No konkretne se koukni na tohle:

Mas gramatiky G1 a G2 nejake (KT, BKT, BPF, typu 0, monotonni, libovolna, regularni, linearni, prave regularni, v chomskeho forme -- ma tam snad vsechny varianty, ja mel ze mas 2 libovolne) a mas rict jestli jsou uzavrene na prunik/doplnek/konecny prunik/spocetny prunik/nespocetny prunik/iteraci/ablabla, vsechno mozne.
Potom vztahy (L(G1) cokoliv L(G2))* ?? L(G1)* cokoliv L(G1)*.

Pak se koukni na ruzne specialni formy automatu, turinguv s dvema hlavama, zasobnikovy s dvema zasobnikama, turinguv s ruzne omezenou paskou, a ruzne vztahy mezi jazyky, ktere generuji.

Kdyz budes umet tohle, tak das minimalne pulku toho zaskrtavaciho testu.

Jeste mi prislo, ze tam byly tak tri otazky na ruzne vztahy mezi izomorfismem/homomofrismem/ekvivalenci/redukovanym automatem/neredukovanym automatem.

To by bylo asi tak k tomu testu.

A na druhou cast uz je to loterie, co si vytahnes a jak to vymyslis, ale v zasade uz nevyletis, pokud znas zakladni definice. Vsiml jsem si, ze kazdemu, kdo je na trojku dal jako posledni otazku napsat chomskeho hierarchii, vsechny definice automatu a gramatik a vztahy, co v ni jsou. To asi nesmis podelat a mas za 3.

Nemuzes (myslim Medveda) uverejnit ve foru tvoje zapisky na uceni ATOGRA?

Leda, ze by sis pro ne nekam dosla a ja bych ti je pujcil na naskenovani, protoze jsem si to psal vsechno rucne.

Jak je to s tím spočetným a nespočetným průnikem? Nějak si nedovedu představit, že by na to moh bejt nějakej jazyk uzavřenej....to by automat, kterej ho rozpoznává, musel mít nekonečně stavů, ne?