Zk 22.5.2007 8:00

Zkouska mela dve casti

1. Kviz (29 otazek) - k postupu do dalsi casti bylo nutno ziskat 20 bodu (1 otazka = 1 bod)
   V kvizu byly otazky a k nim odpovedi, pricemz spravnych odpovedi bylo 0 - vsechny. Nektere otazky docela neprijemne zakerne - obcas nejaky chytacek

2. Priklad - behem zkousky jsem si vsiml ze v tehle casti se to lisilo (ne vsichni meli stejny priklad)

Priklady typu sestrojte automat, gramatiku, napsat nejakou definici a urcite nejaky dalsi libustky.
U prikladu bylo pozadovano dokazani potrebnych vet apod.

Uspesnost nevim - vetsina lidi to ale nedala (vcetne me malickosti)

Tak preju vic stesti v dalsich terminech

Pokud mezi dvema konecnymi automaty A1 A2 existuje homomorfismus, oznacte spravna tvrzeni:
a) A1 a A2 maji stejny pocet stavu
b) A1 a A2 maji stejny pocet koncovych stavu
c) A1 a A2 maji stejny pocet pocatecnich stavu

Jaky jazyk prijima nedeterministicky turinguv stroj?

Bezkontextovy bezprefixovy jazyk je prijiman:
a) zasobnikovym automatem koncovym stavem
b) zasobnikovym automatem prazdnym zasobnikem
c) deterministickym zasobnikovym automatem koncovym stavem
d) deterministickym zasobnikovym automatem prazdnym zasobnikem

Jsou-li A1 a A2 ekvivalentni deterministicke konecne automaty, oznacte spravna tvrzeni:
a) A1 a A2 jsou izomorfni
b) existuje homomorfismus mezi A1 a A2
c) L(A1)=L(A2)
d) A1 a A2 maji stejny pocet koncovych stavu

Prunik bezkontextoveho jazyka a regularniho jazyka je:
a) regularni jazyk
b) bezkontextovy jazyk
c) rekurzivne spocetny jazyk
d) kontextovy jazyk

Doplnek rekurzivne spocetneho jazyka je:
a) rekurzivni jazyk
b) regularni jazyk
c) rekurzivne spocetny jazyk

Jaky je jazyk generovany Linearnimi gramatikami?

Pokud A=(Q,X,d,S,F) je nedeterministicky konecny automat, jaky jazyk prijima automat:
B=(Q,X,d,S,(Q-F))?
a) L(A)^R
b) X* - L(A)
c) L(A)
d) X*

.....

Zneni otazek neni mozna uplne presne....

No to teda, bola sranda. :roll:

Pridavam zopar otazok, ktore si pamatam.

Zadane 2 jazyky L1={a} L2={b}
L=(L1 U L2)*, ktore zo slov patria do jazyka:
a) aa
b) aba
c) abb
d) ab

Co sa stane po vyprazdneni zasobnika:
a) vypocet konci
b) vlozi sa pociatocny symbol
c) nico z prechod. fciami (ze sa uplatnuju iba tie alebo tak nejak)
d) ?

Nech ~i je eqvivalencia po i krokoch, potom pre (asi) KA plati
a) p ~i q => p ~i+1 q
b) p ~i+1 q => p ~i q
c) ?
d) ?

Ak ma gramatika G najmensi pocet stavov ako ktorakolvek ina gramatika generujuca ten isty jazyk potom je:
a) redukovana
b) nemusi byt redukovana
c) ?
d) ?

Ak je L rekurzivne spocetny, potom -L je
a) rekurzivny
b) rekurzivne spocetny
c) regularny
d) ?

Ake jazyky prijma TS
a) typu 0
b) rekurzivne spocetne
c) bezkontextove
d) vsetky

Bol zadany netererministicky automat A (tusim 4 stavovy)
do akych stavov sa mozeme dostat lubovolnym slovom |W|= 2 L(A)
a) A
b) B
c) C
d) D
(tusim to bol chytak bo chybala, hrana so symbolom a)

Pre slovo w mate zadany derivacny strom, potom tento strom urcuje:
a) vsetky mozne derivacie
b) pravu derivaciu/e
c) lavu derivaciu/e
d) ?

Otazky, ktore si uz fakt nepametam. Snad niekomu nieco pripomenu a doplni ma:

Bol "zadany" (formalne) automat, kde delta je priblizne QxXxQ (toto nieje def obor ale potom fakt neviem co to je) skratka to bolo zadane inak.
a) je to zasobnikovy nedeterministicky automat
b) zasobnikovy deterministicky automat
c) KA
d) ?

Za otazky nerucim a ani za odpovede. Je dost pravdepodobne, ze z 2ch otazok vznikla jedna alebo z odpovede vznikla otazka. :twisted:

Este by som podotkol, ze na polbody sa nehra. Skratka mas - nemas....
Inak si dajte pozor na vsetky slova v zadani, pretoze ako povedal, kazde SLOVO ma svoj vyznam. Skratka tam bolo dost vela chytakov, teda aspon mne sa zdalo :x

Otazka:

Je obecne mozne ziskat doplnek regularniho jazyka prohozenim koncovych a
nekoncovych stavu v nedeterministickem automatu?

Mam takove tuseni ze odpoved je NE, ale nevim presne proc....

Ja se take domnivam ze NE.

p ---(a)--->q1
p ---(a)--->q2

F = {q1}

Pocatecni stav = p

Tendle automat prijme slovo "a"

Pokud prohodim F' = Q - F = {p,q2}
Tak automat prijme {lambda, "a"}
Tedy urcite neni doplnkem.

[Edit] Nevite nekdo jeste jak je to s rekurzivne spocetnyma jazykama a jejich doplnkem?

Kdyz mam tuhle otazku:

Ake jazyky prijma TS
a) typu 0
b) rekurzivne spocetne
c) bezkontextove
d) vsetky

tak jaka je odpoved? Vim ze a i b, ale bezkonetxtove jsou jejich podmnozinou, tak i c? a pod deckem si mam predstavit, vsechny jazyky chomskeho hierarchie nebo nebo vsecky drive vyjmenovane? Pokud by to byly vsechny chomskeho, tak by byla spravnou odpovedi i d, ne?

Sakuri wrote: deckem si mam predstavit, vsechny jazyky chomskeho hierarchie nebo nebo vsecky drive vyjmenovane? Pokud by to byly vsechny chomskeho, tak by byla spravnou odpovedi i d, ne?

No v podstate si myslim ze mas pravdu ... ale slovo vsetky moze podla mna znamenat aj vsetky na svete ... a co ak sa TS nad nejakym jaykom nezastavi? potom nemozes povedat ze rozpoznava vsetky :roll:

nejsem si jist, jestli rozpoznan po nekonecne dobe znamena nerozpoznan, ale zajimalo by me, jestli bys mel priklad takoveho jazyka, nejak si ho nedovedu predstavit.

hippies wrote:nejsem si jist, jestli rozpoznan po nekonecne dobe znamena nerozpoznan, ale zajimalo by me, jestli bys mel priklad takoveho jazyka, nejak si ho nedovedu predstavit.

Staci vedet, ze takovy jazyk existuje. Kdyby neexistoval, tak bys umel resit Halting problem. ;)

Ne kazdy jazyk je rekurzivne spocetny, viz napriklad Halting problem, Postuv korespondencni problem, automaticke dokazovani...

odpoved vsechny je spatne