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:
Re: Kvíz Barták 20. 5. 2012
15) Vlastnost "existuje přirozené číslo n takové, že libovolné slovo lze psát ve tvaru uvw,kde: |vw|=<n,1=<|v| a pro
všechna i>=0 platí " 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)
všechna i>=0 platí " 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)
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
16) Pro redukovaný automat a libovolný ekvivalentní platí
a)
b) všechny stavy jsou ekvivalentní
c) A má aspoň 1 výstupní stav
d)
odpověď: ad
(a - redukt obsahuje jen dosažitelné stavy
d - ve spojení s a) bude příslušné slovo )
a)
b) všechny stavy jsou ekvivalentní
c) A má aspoň 1 výstupní stav
d)
odpověď: ad
(a - redukt obsahuje jen dosažitelné stavy
d - ve spojení s a) bude příslušné slovo )
Naposledy upravil(a) mathemage dne 31. 5. 2012 14:36, 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
17) Buď nedeterministický konečný automat. Pak automat 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))
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))
Naposledy upravil(a) mathemage dne 31. 5. 2012 20:05, celkem upraveno 1 x.
Carpe Diem!
Re: Kvíz Barták 20. 5. 2012
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).mathemage píše:17) Buď nedeterministický konečný automat. Pak automat 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)
-
- 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
Tohle mi nejak neni jasne: kdyz , pak obecne neplati , ale naopak . Kdybych chtel , potrebuji .brunclik píše: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).
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 (jinak by puvodni automat prijimal vse a doplnek by byl prazdny, tedy by SLO o nadmnozinu -L(A))
Ale stejne nechapu argument:
Tady preci nejde o podmnozinu stavu Q-F, ale jazyk, ktery je prijimany automatem s prohozenymi koncovymi stavy...brunclik píše:protože Q-F je prázdná, což není nadmnožina -L(A)
Ale mozna jsem to jen spatne pochopil... spis bych rekl, ze problem bude v tom, jak jsem psal vyse...
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
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)
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)
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
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)
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)
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
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??)
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??)
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
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...
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...
Carpe Diem!
-
- Matfyz(ák|ačka) level I
- Příspěvky: 8
- Registrován: 19. 1. 2011 15:45
- Typ studia: Informatika Bc.
- Login do SIS: tesarka
Re: Kvíz Barták 20. 5. 2012
d taky ne: přijme např. 10110.mathemage píše: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...
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.
Re: Kvíz Barták 20. 5. 2012
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).Ganef píše:
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.
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.
Re: Kvíz Barták 20. 5. 2012
Pardon, 'a' jazyk generuje, jsem si neuvedomil, ze je na zacatku v zavorce 0*eldros píše: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).Ganef píše:
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.
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.
Re: Kvíz Barták 20. 5. 2012
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.
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.
-
- 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
Ahoj,Semi píše: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.
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
Carpe Diem!