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:

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

Příspěvek od mathemage »

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

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))
Naposledy upravil(a) mathemage dne 31. 5. 2012 14:36, 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 »

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))
Naposledy upravil(a) mathemage dne 31. 5. 2012 20:05, celkem upraveno 1 x.
Carpe Diem!
brunclik

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

Příspěvek od brunclik »

mathemage píše: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).
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 »

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).
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 píše: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...
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 »

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

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

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

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...
Carpe Diem!
Ganef
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 19. 1. 2011 15:45
Typ studia: Informatika Bc.

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

Příspěvek od Ganef »

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

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

Příspěvek od eldros »

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

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

Příspěvek od eldros »

eldros píše:
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.
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* :)
Semi

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

Příspěvek od Semi »

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

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

Zpět na „TIN071 Automaty a gramatiky“