Zkoušítko na zkouškovej kvíz

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

Zkoušítko na zkouškovej kvíz

Příspěvek od dj-bulva »

Ahoj,
tak dneska to na zkoušce bylo pro ostatní asi v pohodě, pro mě pěkný nervy. Bylo nás tak 20, kvízem neprošli tak 4. Já tam zůstal předposlední a všichni přede mnou ústní dali v pohodě. Já jsem měl otázku na sestrojení gramatiky z Turingova stroje a důkaz toho že to jde a jak se to dělá, což jsem vůbec nevěděl. Měl jsem ale docela slušnej kvíz (24 b), tak se mě zeptal, jaký mám ambice a já že na trojku. Tak mi dal definovat všechny automaty v Chomského hierarchii. To bylo v pohodě, tak ještě chtěl vědět, jak vypadají pravidla gramatik v celý tý hierarchii. To jsem taky dal a mám za 3. K tomu kvízu asi dost přihlíží, když měl někdo 19 nebo 18 bodů, tak dělal jako že "ajeje, to se ještě na něco zeptám".

No ale chtěl jsem se taky s budoucí generací podělit o jednoduchý "kvízovátko", který jsem zprgnul v PHPku, a kam jsem přepsal všechny zodpovězený otázky z kvízu, co jsem kde našel. Ke stažení je to zde: http://uloz.to/xS88QBE/zkousitko-na-automaty-zip Je tam asi 120 otázek. Za chyby pochopitelně neručím, a dávám svolení s tím nakládat libovolně, např. kdyby někdo měl chuť to někam nasadit na web, případně rozšířit o další otázky.
jans
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 31. 5. 2012 12:29
Typ studia: Informatika Bc.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od jans »

Zdravím, trochu jsem to ještě přepracoval a hodil k sobě na stránky pro ty, kteří nemají instalováno PHP, pořp. si jej instalovat nechtějí nebo jsou moc líní.

http://www.skvaril.net/cz/automaty/
dj-bulva

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od dj-bulva »

Moc pěkné, ještě bys tam mohl doplnit otázky, které sem dává *mathemage*: http://forum.matfyz.info/viewtopic.php?f=243&t=8286

Jo a ještě bych chtěl upozornit na jednu otázku, konkrétně:

Kód: Vybrat vše

Ve stavovém diagramu libovolného deterministického konečného automatu (hrana je určena dvojicí stavů a písmenem) vede z každého stavu:
A) právě tolik hran kolik je písmen v abecedě
B) právě jedna hrana
C) alespoň jedna hrana
D) méně hran než kolik je stavů
Tuhle otázku jsem tu někde našel na fóru zodpovězenou, s odpovědí jenom "A". Ale já bych dal "AC", protože imho musí být abeceda neprázdná. Imho to je zkoušítku označeno jenom jako "A", tak to kdyžtak oprav.
jans
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 31. 5. 2012 12:29
Typ studia: Informatika Bc.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od jans »

Díky, otázku jsem opravil, myslím, že tam asi bude chyb více, když bych něco objevil, tak to sem napíšu. Ty zbylé tam doplním někdy během příštího týdne.
maky
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 24. 1. 2010 15:25
Typ studia: Informatika Mgr.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od maky »

super udělátko, díky moc :)

u otázky 95, (týká se ekvivalentních stavů - nechce se mi to sem přepisovat) není uvedena správně žádná možnost, ale viz slajdy by měla podle mě být správně odp. 0. (je to definice)
pokud se mýlim, tak se omlouvám a případně prosím o vysvětlení.
jans
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 31. 5. 2012 12:29
Typ studia: Informatika Bc.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od jans »

Ta odpověď je správně. Pozor, u tý otázky se jedná o NKA, neboť je tam S jako množina počátečních stavů, tedy ani jedna z odpovědí nedává smysl.
maky
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 24. 1. 2010 15:25
Typ studia: Informatika Mgr.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od maky »

pravda, omlouvám se, to jsem přehlédla.
jans
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 31. 5. 2012 12:29
Typ studia: Informatika Bc.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od jans »

Zdravím, tak jsem tam tedy doplnil ještě otázky od mathemage.
mira

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od mira »

Ahoj,

u otazky 44) Jazyk {1^k 1^k 0^l | k, l >= 0} je podle me spravne i odpoved regularni. Je to prece {1^2k 0^l | k, l >= 0} a protoze neni definovany zadny vztah mezi k a l, tak k tomu jde jednoduse sestrojit automat, ktery ten jazyk prijme.

Mira
jans
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 31. 5. 2012 12:29
Typ studia: Informatika Bc.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od jans »

Ahoj, to je nepochybně pravda, díky za upozornění, už jsem to tam opravil.
do

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od do »

Zdravim,

otazka 29) pumping lemma plati pro jazyky:

spravna odpoved je uvedena "regularni, bezkontextove a kontextove" a pro kontextove jazyky rozhodne neplati (protipriklad na slidech - a^i b^j c^k (1 <= i <= j <= k) nemuzu nikde pumpovat pro vsechna cisla od nuly vcetne, protoze kazde pismeno tam musi byt aspon jednou. A i kdyby, libovolnym pumpovanim v kterekoli casti drive ci pozdeji porusim nejakou nerovnost.
Merlin
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 3. 2. 2008 01:00
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od Merlin »

Ahoj

Otázka 86)
Správně by mělo být (0*10*1)*0* a 0*(10*1)*0*

Ad otázka 29)
Tady by podle mě mělo být správně jenom regulární, protože pro bezkontextové jazyky ta věta zní trochu jinak.

Jestli nemám pravdu, tak mě opravte.

Jinak by bylo fajn mít možnost zobrazit správné odpovědi k vybrané otázce -> tzn. v zobrazení všech otázek buď správné odpovědi vyznačit nebo po kliku na tlačítko "Zobrazit test" zobrazit zvolenou testovou otázku.

//Edit:
Tak jsem se dneska na zkoušce přesvědčil, že moje doměnka k otázce 29 je špatně :D
PS: až se budete učit na zkoušku a budete si říkat, že ty největší hnusárny tam být nemůžou... Můžou :D
Danstahr
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 26. 1. 2012 18:50
Typ studia: Informatika Bc.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od Danstahr »

Ahoj, myslím, že je chyba u následujících otázek :

75) Nedeterministický konečný automat má n stavů. Počet stavů po převodu na deterministický nebude větší než:
  • nelze říci
  • 2^n stavů
  • n^n stavů
  • n stavů
Jako správné je označeno b a c, ale pro n^n to nebude fungovat pro n = 1. Pokud budeme mít automat s jedním stavem (vstupním a výstupním zároveň), abecedu {0, 1} a smyčku třeba pro 1, nedeterministickému automatu absence nuly nevadí, jenže v deterministickém potřebujeme nějaký "věčně nepřijímající" stav.
Naposledy upravil(a) Danstahr dne 24. 6. 2013 15:49, celkem upraveno 1 x.
mjk
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 6. 9. 2011 17:40
Typ studia: Informatika Bc.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od mjk »

Ta otázka 29 je nějaká divná. Tak jak je napsaná v ní chybí podmínka |v| >= 1, takže si vybereme v = \lambda a jelikož z = uvw = uw \in L, tak i uv^iw = uw \in L pro i >= 0. To by snad mělo platit pro všechny jazyky.
mjk
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 6. 9. 2011 17:40
Typ studia: Informatika Bc.

Re: Zkoušítko na zkouškovej kvíz

Příspěvek od mjk »

Otázka 102:

Řekneme, že dva stavy p a q konečného automatu A = (Q,X,\delta,S,F) jsou ekvivalentní právě tehdy, když

\forall w \in X^* : \delta^*(p,w) = \delta^*(q,w)
\forall w \in L(A) : \delta^*(p,w) \in F \Leftrightarrow \delta^*(q,w) \in F
\forall w \in L(A) : \delta^*(p,w) = \delta^*(q,w)
\forall w \in X^* : \delta^*(p,w) \in F \Leftrightarrow \delta^*(q,w) \in F

Žádná odpověď není označena jako správná, ale pokud dobře vidím, tak ta poslední přesně odpovídá definici ve slidech... přehlížím něco?
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“