Kvíz Barták 20. 5. 2012

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).
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

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!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

1) Pro libovolny jazyk je L^+ roven
a) \{u^i | u \in L, i >= 0\}
b) \{u^i | u \in L, i >= 1\}
c) L^* - \{\lambda\}
d) \bigcup_{i>=1} L^i

Odpověď: d
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

2) Pro L=\{a, b, \lambda\} je L^2 roven
a) \{ab, ba\}
b) \{aa, bb\}
c) \{ab, ba, aa, bb\}
d) \{a, b, aa, ab, ba, bb\}

Odpověď: nic (chybi lambada]
Naposledy upravil(a) mathemage dne 30. 5. 2012 23:31, celkem upraveno 1 x.
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

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)
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

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)
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

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)
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

6) Deterministicke zasobnikove automaty rozpoznaji prazdnym zasobnikem vsechny jazyk
a) regularni
b) bezkontextove bezprefixove
c) bezkontextove
d) rekurzivne spocetne

odpoved: b (viz slidy)
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

7) Necht A je trida bezkontextovych jazyku, B je trida deterministickych bezkontextovych jazyku, pak plati
a) A = B
b) A 
e B
c) A \subseteq B
d) A \supseteq B

odpoved: bd (viz slidy)
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

8) Necht L1 a L2 jsou jazyky nad stejnou abecedou takove, ze L1\subset L2(L1
e L2) 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 - 01 \subset 0^n1^n
b - 0^n1^n \subset 0^*1^*
c - 01 \subset 0^n1^n
d - L1 je pak konecny, to snadno napisu nejakym regexem
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

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) 
e 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!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

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)
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

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)
Naposledy upravil(a) mathemage dne 4. 6. 2012 00:10, celkem upraveno 1 x.
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

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#)
Naposledy upravil(a) mathemage dne 31. 5. 2012 11:18, celkem upraveno 1 x.
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

13) Necht dva stavy p a q (deterministickeho) konečného automatu A=(Q, X, \delta, q_0, F) 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 + L(A) \subseteq X^* )
Naposledy upravil(a) mathemage dne 15. 6. 2012 10:49, celkem upraveno 2 x.
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Kvíz Barták 20. 5. 2012

Příspěvek od mathemage »

14) Pro pravou (syntaktickou) kongruenci na X^* plati:
a) je to ekvivalence
b) ma konecny index
c) \forall u,v,w \in X^*: u \sim v \rightarrow uw \sim vw
d) \forall u,v \in X^*: u = v \rightarrow u \sim v

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!
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“