Kvíz Barták 20. 5. 2012
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Kvíz Barták 20. 5. 2012
Otazky z dnesniho quizu (budu pridavat otazku po otazce podle toho, jak si budu vzpominat). Kdyz si nekdo dalsi na dalsi otazky vzpomenete (nebo si treba vsimnete chyby v moznostech/v odpovedi...), nevahejte pripsat
Naposledy upravil(a) mathemage dne 30. 5. 2012 22:41, celkem upraveno 2 x.
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
2) Pro je roven
a)
b)
c)
d)
Odpověď: nic (chybi lambada]
a)
b)
c)
d)
Odpověď: nic (chybi lambada]
Naposledy upravil(a) mathemage dne 30. 5. 2012 23:31, celkem upraveno 1 x.
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
3) Deterministicke bezkontextove jazyky jsou uzavrene na
a) sjednoceni
b) prunik
c) doplnek
d) substituce
odpoved: c (viz slidy: u d) dokazano pro homomorfismus, coz je specialni substituce)
a) sjednoceni
b) prunik
c) doplnek
d) substituce
odpoved: c (viz slidy: u d) dokazano pro homomorfismus, coz je specialni substituce)
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
4) Problem ekvivalence dvou bezkontextovych gramatik je algoritmicky ekvivalentni
a) problemu zastaveni Turingova stroje
b) Postovu korespondencnimu problemu
c) Postovu korespondencnimu problemu s inicialnim resenim
d) problem, zda je bezkontextovy jazyk prazdny
odpoved: abc (viz slidy: vse je algoritmicky nerozhodnutelne, krom d), kde staci pouzit algoritmus redukce)
a) problemu zastaveni Turingova stroje
b) Postovu korespondencnimu problemu
c) Postovu korespondencnimu problemu s inicialnim resenim
d) problem, zda je bezkontextovy jazyk prazdny
odpoved: abc (viz slidy: vse je algoritmicky nerozhodnutelne, krom d), kde staci pouzit algoritmus redukce)
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
5) Prunik dvou bezkontextovych jazyku je jazyk
a) regularni
b) bezkontextovy
c) rekursivni
d) rekursivne spocetny
odpoved: cd - nejsem si jist, 1 ze 3 mych spatnych odpovedi
(c - nalezitost slova do BKJ je ze slidu algoritmicky rozhodnutelne, tudiz existuje TS i pro oba doplnky a tim i doplnek pruniku... asi takhle, tohle jsem spatne nezaskrtl...
d - paralelni beh obou prislusnych Turingovych stroju)
a) regularni
b) bezkontextovy
c) rekursivni
d) rekursivne spocetny
odpoved: cd - nejsem si jist, 1 ze 3 mych spatnych odpovedi
(c - nalezitost slova do BKJ je ze slidu algoritmicky rozhodnutelne, tudiz existuje TS i pro oba doplnky a tim i doplnek pruniku... asi takhle, tohle jsem spatne nezaskrtl...
d - paralelni beh obou prislusnych Turingovych stroju)
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
6) Deterministicke zasobnikove automaty rozpoznaji prazdnym zasobnikem vsechny jazyk
a) regularni
b) bezkontextove bezprefixove
c) bezkontextove
d) rekurzivne spocetne
odpoved: b (viz slidy)
a) regularni
b) bezkontextove bezprefixove
c) bezkontextove
d) rekurzivne spocetne
odpoved: b (viz slidy)
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
7) Necht A je trida bezkontextovych jazyku, B je trida deterministickych bezkontextovych jazyku, pak plati
a)
b)
c)
d)
odpoved: bd (viz slidy)
a)
b)
c)
d)
odpoved: bd (viz slidy)
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
Necht L1 a L2 jsou jazyky nad stejnou abecedou takove, ze Potom platí:
a) je-li L1 prijiman koncenym automatem, potom je L2 přijiman konecnym automatem
b) je-li L2 prijiman koncenym automatem, potom je L1 přijiman konecnym automatem
c) je-li L1 konecny, potom je L2 přijiman konecnym automatem
d) je-li L2 konecny, potom je L1 přijiman konecnym automatem
odpoved: d
a -
b -
c -
d - L1 je pak konecny, to snadno napisu nejakym regexem
a) je-li L1 prijiman koncenym automatem, potom je L2 přijiman konecnym automatem
b) je-li L2 prijiman koncenym automatem, potom je L1 přijiman konecnym automatem
c) je-li L1 konecny, potom je L2 přijiman konecnym automatem
d) je-li L2 konecny, potom je L1 přijiman konecnym automatem
odpoved: d
a -
b -
c -
d - L1 je pak konecny, to snadno napisu nejakym regexem
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
9) Nechť G1=(N1,T, S1,P1) a G2=(N2,T, S2,P2) jsou dvě kontextové gramatiky s disjunktními množinami neterminálů
(N1,N2) a S je nový neterminál. Potom pro jazyk gramatiky G=(N1∪N2∪{S},T,S,P1∪P2∪{S->S1S2}) platí:
a) L(G) L(G1) . L(G2)
b) L(G) = L(G1) . L(G2)
c) L(G) ⊆ L(G1) . L(G2)
d) L(G) ⊇ L(G1) . L(G2)
odpoved: d (u moznosti b) muzou zapracovat i terminaly na rozhrani S1S2, ale nemusi to vzdycky nastat - napr. u BKG - proto ani moznost a) )
(N1,N2) a S je nový neterminál. Potom pro jazyk gramatiky G=(N1∪N2∪{S},T,S,P1∪P2∪{S->S1S2}) platí:
a) L(G) L(G1) . L(G2)
b) L(G) = L(G1) . L(G2)
c) L(G) ⊆ L(G1) . L(G2)
d) L(G) ⊇ L(G1) . L(G2)
odpoved: d (u moznosti b) muzou zapracovat i terminaly na rozhrani S1S2, ale nemusi to vzdycky nastat - napr. u BKG - proto ani moznost a) )
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
10) Mezi ekvivalenci stavu a automatovou kongruenci je vztah
a) kazda automatova kongruence je ekvivalence stavu
b) kazda ekvivalence stavu je automatova kongruence
c) jsou to 2 pojmy pro totez
d) neni mezi nimi jasne definovany vztah
odpoved: b (viz slidy)
a) kazda automatova kongruence je ekvivalence stavu
b) kazda ekvivalence stavu je automatova kongruence
c) jsou to 2 pojmy pro totez
d) neni mezi nimi jasne definovany vztah
odpoved: b (viz slidy)
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
11) Turinguv stroj, ktery se po pasce posouva jen doprava (tj. muze zustat na miste nebo se posunout, ale jen doprava), prijima jazyky, ktere prijima i:
a) konecny automat
b) dvoucestny konecny automat
c) zasobnikovy automat
d) linearne omezeny automat
odpoved: Vysoka Skola Ekonomicka (paska je nam vlastne k nicemu, staci nam jen konecne stavu, proto tento TS ma silu pouheho KA a regularni jazyky prijimaji vsechny vyse uvedene - tedy VSE)
a) konecny automat
b) dvoucestny konecny automat
c) zasobnikovy automat
d) linearne omezeny automat
odpoved: Vysoka Skola Ekonomicka (paska je nam vlastne k nicemu, staci nam jen konecne stavu, proto tento TS ma silu pouheho KA a regularni jazyky prijimaji vsechny vyse uvedene - tedy VSE)
Naposledy upravil(a) mathemage dne 4. 6. 2012 00:10, celkem upraveno 1 x.
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
12) Pro 2 automaty A a B prijimajici stejny jazyk L plati:
a) A je ekvivalentni B
b) A je isomorfni B
c) A je identicky B
d) mezi A a B existuje homomorfismus (z A do B nebo z B do A)
odpoved: a
(u d) jsem si fakt nebyl jist, ale protipriklad:
2 automaty se stejnou strukturou: vstupni stav jedinym koncovym stavem + k nemu navic 2 nedosazitelne stavy mimo ve tvaru 2-cyklu se smyckou v obou vrcholech - takovy ten lanovy posilac rukou/prsou, co pouzivaj kulturisti
v 1. automatu na smyckach budou "a" a na klasickych hranach "b"
v 2. automatu naopak pismenka
oba prijimaji stejny jazyk, ale u nedosazitelnych stavu neexistuje homomorfismy ani z jedne strany <- zatimco v jednom nejakym pismenkem zustavam na miste, v tom druhem automatu se vzdy pohnu jinam #spor#)
a) A je ekvivalentni B
b) A je isomorfni B
c) A je identicky B
d) mezi A a B existuje homomorfismus (z A do B nebo z B do A)
odpoved: a
(u d) jsem si fakt nebyl jist, ale protipriklad:
2 automaty se stejnou strukturou: vstupni stav jedinym koncovym stavem + k nemu navic 2 nedosazitelne stavy mimo ve tvaru 2-cyklu se smyckou v obou vrcholech - takovy ten lanovy posilac rukou/prsou, co pouzivaj kulturisti
v 1. automatu na smyckach budou "a" a na klasickych hranach "b"
v 2. automatu naopak pismenka
oba prijimaji stejny jazyk, ale u nedosazitelnych stavu neexistuje homomorfismy ani z jedne strany <- zatimco v jednom nejakym pismenkem zustavam na miste, v tom druhem automatu se vzdy pohnu jinam #spor#)
Naposledy upravil(a) mathemage dne 31. 5. 2012 11:18, celkem upraveno 1 x.
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
13) Necht dva stavy p a q (deterministickeho) konečného automatu jsou ekvivalentní, potom plati:
a) ∀w∈X* δ*(p,w)∈F⇔δ*(q,w)∈F
b) ∀w∈X* δ*(p,w) = δ*(q,w)
c) ∀w∈L(A) δ*(p,w)∈F⇔δ*(q,w)∈F
d) ∀w∈L(A) δ*(p,w) =δ*(q,w)
odpoved: ac (viz slidy + )
a) ∀w∈X* δ*(p,w)∈F⇔δ*(q,w)∈F
b) ∀w∈X* δ*(p,w) = δ*(q,w)
c) ∀w∈L(A) δ*(p,w)∈F⇔δ*(q,w)∈F
d) ∀w∈L(A) δ*(p,w) =δ*(q,w)
odpoved: ac (viz slidy + )
Naposledy upravil(a) mathemage dne 15. 6. 2012 10:49, celkem upraveno 2 x.
Carpe Diem!
-
- Matfyz(ák|ačka) level III
- Příspěvky: 130
- Registrován: 14. 1. 2011 10:03
- Typ studia: Informatika Ph.D.
- Login do SIS: had
- Kontaktovat uživatele:
Re: Kvíz Barták 20. 5. 2012
14) Pro pravou (syntaktickou) kongruenci na plati:
a) je to ekvivalence
b) ma konecny index
c)
d)
Odpověď: acd (posledni moznost je jen krypticky popsana reflexivita ekvivalence)
a) je to ekvivalence
b) ma konecny index
c)
d)
Odpověď: acd (posledni moznost je jen krypticky popsana reflexivita ekvivalence)
Naposledy upravil(a) mathemage dne 31. 5. 2012 11:19, celkem upraveno 1 x.
Carpe Diem!