# Kvíz Barták 20. 5. 2012

<{ForumPost(poster="mathemage", timestamp=2012-05-30 21:36:37)}>
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 :-)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 21:37:36)}>
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
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 22:14:26)}>
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]
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 22:36:11)}>
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)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 22:40:10)}>
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)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 22:46:03)}>
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)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 22:48:41)}>
6) Deterministicke zasobnikove automaty rozpoznaji prazdnym zasobnikem vsechny jazyk  
a) regularni  
b) bezkontextove bezprefixove  
c) bezkontextove  
d) rekurzivne spocetne  
  
odpoved: b (viz slidy)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 22:52:48)}>
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)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 22:57:40)}>
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
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 23:01:32)}>
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) )
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 23:04:57)}>
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)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 23:10:06)}>
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)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 23:21:44)}>
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#)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 23:30:46)}>
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^*$ )
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-30 23:34:39)}>
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)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-31 10:27:37)}>
15) Vlastnost "existuje přirozené číslo n takové, že libovolné slovo $z \in L,|z|>=n$ lze psát ve tvaru uvw,kde: |vw|=<n,1=<|v| a pro  
všechna i>=0 platí $uv^iw \in L$" je nutnou podmínkou pro jazyky:  
a) regulární  
b) bezkontextové  
c) kontextové  
d) rekursivně spočetné  
  
odpověď: a (obdoba pumping lemmatu pro regulární jazyky, důkaz lze provést analogicky pro poslední ze stavů, který se zopakoval)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-31 11:51:51)}>
16) Pro redukovaný automat $A = (Q, X, \delta, q_0, F)$ a libovolný $q \in Q$ ekvivalentní platí  
a) $\exists u \in X^*: \delta^*(q_0, u) = q$  
b) všechny stavy jsou ekvivalentní  
c) A má aspoň 1 výstupní stav  
d) $q \in F \Rightarrow L(A) 
e \emptyset$  
  
odpověď: ad   
(a - redukt obsahuje jen dosažitelné stavy  
d - ve spojení s a) bude příslušné slovo $u \in L(A)$)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-31 14:36:35)}>
17) Buď $A = (Q, X, \delta, q_0, F)$ nedeterministický konečný automat. Pak automat $A = (Q, X, \delta, q_0, Q-F)$ přijímá právě jazyk  
a) -L(A)  
b) L(A)  
c) který je nadmnožinou -L(A)  
d) který je nadmnožinou L(A)  
  
odpověď: tady jsem zaškrtl c, ale když tak o tom přemýšlím, nemůže to být správně (pokud nebudou z nekoncového stavu definovány kroky dál, selže v obou automatech, i když jde o slovo z -L(A)... tady mne opravte někdo, kdo jste to měl správně...  
(a - nelze, v NKA můžou vést zároveň cesty nad jedním slovem zároveň do koncových i nekoncových stavů, prohozením koncových stavů s nekoncovými to stále bude mišmaš a přijme i slova z L(A))
<{/ForumPost}>

<{ForumPost(poster="brunclik", timestamp=2012-05-31 15:51:07)}>

 > mathemage wrote:17) Buď $A = (Q, X, \delta, q_0, F)$ nedeterministický konečný automat. Pak automat $A = (Q, X, \delta, q_0, Q-F)$ přijímá právě jazyk  
 > a) -L(A)  
 > b) L(A)  
 > c) který je nadmnožinou -L(A)  
 > d) který je nadmnožinou L(A)

Správně není ani jedno. A i B se vyloučí snadno, pokud v původním automatu je F = Q, pak vyloučím i možnost D (Q-F je prázdná, což určitě není nadmnožina). Naopak, když je v původním F prázdná množina, tak vyloučím C, protože Q-F je prázdná, což není nadmnožina -L(A) (původní nepřijímal nic, doplněk je všechno).
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-31 20:03:14)}>

 > brunclik wrote:Naopak, když je v původním F prázdná množina, tak vyloučím C, protože Q-F je prázdná, což není nadmnožina -L(A) (původní nepřijímal nic, doplněk je všechno).

Tohle mi nejak neni jasne: kdyz $F = \emptyset$, pak obecne neplati $Q-F = \emptyset$, ale naopak $Q-F = Q$. Kdybych chtel $Q-F = \emptyset$, potrebuji $F = Q$.  
  
Problem by mohl byt, kdyby z nejakeho mista nebyl definovan krok dal, pak by se dalo rict, ze neexistuje prislusna cesta do koncoveho stavu a ze $L(A) 
e X^*$ (jinak by puvodni automat prijimal vse a doplnek by byl prazdny, tedy by SLO o nadmnozinu -L(A))  
  
Ale stejne nechapu argument:  

 > brunclik wrote:protože Q-F je prázdná, což není nadmnožina -L(A)

Tady preci nejde o podmnozinu stavu Q-F, ale jazyk, ktery je prijimany automatem s prohozenymi koncovymi stavy...  
  
Ale mozna jsem to jen spatne pochopil... spis bych rekl, ze problem bude v tom, jak jsem psal vyse...
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-05-31 20:08:14)}>
18) Nechť G=(N,T,S,P) je generativní gramatika, pro jejíž pravidla (u → v) platí |u|<=|v|. Pokud neuvažujeme prázdné  
slovo, potom taková gramatika může generovat libovolný jazyk:  
a) regulární  
b) bezkontextový  
c) kontextový  
d) rekurzivně spočetný  
  
odpověď: abc (monotónní je ekvivalentní nějaké kontextové gramatice, která dokáže generovat libovolný jazyk z nižšího levelu Chomského hierarchie)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-06-01 19:52:57)}>
19) Pro algoritmicky rozhodnutelný jazyk L platí:  
a) Existuje Turinguv stroj T prijimajici prave jazyk L  
b) Existuje Turinguv stroj T prijimajici prave jazyk -L  
c) L je linearne omezeny (nebo nejaka jina blbost, ktera neplatila)  
d) L je rekursivni  
  
odpoved: abd (viz Postova veta)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-06-03 23:43:07)}>
20) Na průnik jsou uzavřené jazyky:  
a) regulární  
b) bezkontextové  
c) deterministické bezkontextové  
d) kontextové  
  
odpověď: ad ( d - zřejmě lze simulovat paralelní průběh 2 TS najednou, asi nějak zig zag přesunování po 2-stopé pásce??)
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-06-04 00:00:56)}>
21) Regularni vyraz prijimajici prave jazyky nad abecedou {0, 1} se sudym poctem "1" je:  
a) (0*10*1)*0*  
b) 0*10*1*0*  
c) 0*(10*1)*0*  
d) 0*(10*1*0)*  
  
odpoved: tohle jsem mel spatne, takze newm, ale rekl bych, ze bc urcite ne...
<{/ForumPost}>

<{ForumPost(poster="Ganef", timestamp=2012-06-05 10:30:28)}>

 > mathemage wrote:21) Regularni vyraz prijimajici prave jazyky nad abecedou {0, 1} se sudym poctem "1" je:  
 > a) (0*10*1)*0*  
 > b) 0*10*1*0*  
 > c) 0*(10*1)*0*  
 > d) 0*(10*1*0)*  
 >   
 > odpoved: tohle jsem mel spatne, takze newm, ale rekl bych, ze bc urcite ne...

d taky ne: přijme např. 10110.  
  
a jazyk podle mě generuje. To, že bude sudý počet jedniček je na první pohled vidět a navíc mezi každé dvě jedničky to umí strčit libovolný počet nul.
<{/ForumPost}>

<{ForumPost(poster="eldros", timestamp=2012-06-05 19:02:13)}>

 > Ganef wrote:
 >   
 > d taky ne: přijme např. 10110.  
 >   
 > a jazyk podle mě generuje. To, že bude sudý počet jedniček je na první pohled vidět a navíc mezi každé dvě jedničky to umí strčit libovolný počet nul.

My jsme meli v pondeli podobne, spravne je (0*10*10*)* (z tech, co tu jsou postnuty zadny nesedi zadani 'b' 'c' 'd' jste rekli a 'a' nevygeneruje napr 110110).  
  
Pozor na to 'prave', tzn nestaci ze ty gramatiky generuji jazyk se sudym poctem jednicek (to jde jasne videt az na gramatiku 'd' a 'b'), ta gramatika musi dokazat vygenerovat kazdy jazyk a to neumi.
<{/ForumPost}>

<{ForumPost(poster="eldros", timestamp=2012-06-05 19:06:47)}>

 > eldros wrote:
 >  > Ganef wrote:
 >  >   
 >  > d taky ne: přijme např. 10110.  
 >  >   
 >  > a jazyk podle mě generuje. To, že bude sudý počet jedniček je na první pohled vidět a navíc mezi každé dvě jedničky to umí strčit libovolný počet nul.
 > 
 > 
 > My jsme meli v pondeli podobne, spravne je (0*10*10*)* (z tech, co tu jsou postnuty zadny nesedi zadani 'b' 'c' 'd' jste rekli a 'a' nevygeneruje napr 110110).  
 >   
 > Pozor na to 'prave', tzn nestaci ze ty gramatiky generuji jazyk se sudym poctem jednicek (to jde jasne videt az na gramatiku 'd' a 'b'), ta gramatika musi dokazat vygenerovat kazdy jazyk a to neumi.

Pardon, 'a' jazyk generuje, jsem si neuvedomil, ze je na zacatku v zavorce 0* :)
<{/ForumPost}>

<{ForumPost(poster="Semi", timestamp=2012-06-14 11:43:54)}>
Ahoj,  
myslím, že v otázce číslo 13 máš chybu. Ten automat je nedeterministický (má tam množinu vstupních stavů místo jednoho). Takže i když jsou stavy p, q ekvivalentní neznamená to, že se stejným slovem dostaneme do výstupního stavu v obou případech. Díky nedeterminismu se můžeme rozhodnout jít jinou cestou, která k výsledku nepovede. Tohle platí pro jakékoli slovo. Takže podle mě není správná žádná možnost.
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2012-06-15 10:48:41)}>

 > Semi wrote:Ahoj,  
 > myslím, že v otázce číslo 13 máš chybu. Ten automat je nedeterministický (má tam množinu vstupních stavů místo jednoho). Takže i když jsou stavy p, q ekvivalentní neznamená to, že se stejným slovem dostaneme do výstupního stavu v obou případech. Díky nedeterminismu se můžeme rozhodnout jít jinou cestou, která k výsledku nepovede. Tohle platí pro jakékoli slovo. Takže podle mě není správná žádná možnost.

Ahoj,  
diky za pripominku, mas zcela pravdu, jde o to, ze ja si neuvedomil, ze rikat "konecny automat" muze presto vzbuzovat dojem nedeterminismu (explicitne se rika "nedeterministicky konecny automat"; "deterministicky konecny automat" ma stejnou definici jako "konecny automat" - viz slide 9), takze mi to samozrejme ujelo.   
  
S tim "S" jako pocatecni stavem jsem se upsal, asi jsem to zadani kopiroval odnekud jinud (samozrejme to pujdu hned opravit). Nechtelo se mi to totiz po zkousce uz cely psat - ono je to uz tak dost tezky snazit se vzpominout si na vsech 29 otazek a prislusnych 116 moznosti :-)  
  
Roman taky vyvadel, kdyz se to tam nejaky klucina snazil ofotit - zrovna se bavil s nekym jinym a najednou se v pulce vety zastavil, pristoupil k tomu typkovi zezadu a klidnym, avsak desivym hlasem rekl: "Kopie se nedelaji!" Student jen ahaoval a Bartak si pro sebe zamumlal, proc si vsichni furt chtej delat kopie :-) Takze kdyz uz kopirovat/fotit, chce to sednout si hodne dopredu :-D
<{/ForumPost}>