Fórum studentů MFF UK

od **mathemage** » 15. 6. 2012 10:48

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

od **Semi** » 14. 6. 2012 11:43

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.

od **eldros** » 5. 6. 2012 19:06

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*

od **eldros** » 5. 6. 2012 19:02

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.

od **Ganef** » 5. 6. 2012 10:30

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.

od **mathemage** » 4. 6. 2012 00:00

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

od **mathemage** » 3. 6. 2012 23:43

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

od **mathemage** » 1. 6. 2012 19:52

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)

od **mathemage** » 31. 5. 2012 20:08

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)

od **mathemage** » 31. 5. 2012 20:03

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

od **brunclik** » 31. 5. 2012 15:51

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

od **mathemage** » 31. 5. 2012 14:36

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

od **mathemage** » 31. 5. 2012 11: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)$ )

od **mathemage** » 31. 5. 2012 10:27

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)

od **mathemage** » 30. 5. 2012 23:34

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)

Fórum studentů MFF UK

Kvíz Barták 20. 5. 2012

Odeslat odpověď

Rozšířit náhled Přehled tématu: Kvíz Barták 20. 5. 2012

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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