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 :-)

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

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]

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)

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)

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)

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

odpoved: b (viz slidy)

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)

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

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) )

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)

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)

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#)

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^*$ )

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)

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)

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)$)

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))

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).

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...

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)

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)

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??)

21. Regularni vyraz prijimajici prave jazyky nad abecedou {0, 1} se sudym poctem "1" je:
    a) (0101)0
    b) 01010
    c) 0*(101)0
    d) 0(1010)*

odpoved: tohle jsem mel spatne, takze newm, ale rekl bych, ze bc urcite ne...

mathemage wrote:21) Regularni vyraz prijimajici prave jazyky nad abecedou {0, 1} se sudym poctem "1" je:
a) (0101)0
b) 01010
c) 0*(101)0
d) 0(1010)*

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.

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 (01010*)* (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.

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 (01010*)* (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* :)

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.

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