Testové otázky - aktualizovaná verze

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).
marxin
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 30. 1. 2008 13:24
Typ studia: Informatika Mgr.

Testové otázky - aktualizovaná verze

Příspěvek od marxin »

Po dnešním testu a zkoušce jsem opravil materiály a doplnil nějaké otázky z dnešního testu. Příspěvky jsem dal do incomming na studnici, jinak jsou také ke stažení na následujících odkazech:

http://marxin.eu/docs/1cast_resene_verze2.pdf
http://marxin.eu/docs/1cast_resene_verze2.doc

Co se dá říct k testu, ten dnešní obsahoval nejméně 80% co je obsaženo v dokumentu, ale jak již bylo řečeno, doc. Barták modifikuje drobnosti u jednotlivých testů a proto je potřeba číst pozorně a nevyplňovat podle testovacího dokumentu, stylem se otázka nemusí lišit, odpověďmi však ano.

P.S. Za spolupráci při editaci a kontrole děkuji Martinu Šikovi
Hodně štěstí u zkošky ;)
zvedavec obecny

Re: Testové otázky - aktualizovaná verze

Příspěvek od zvedavec obecny »

Otazka 13: Ja myslim, ze L muze byt prazdny. Nikde neni omezeno, ze w != lambda nebo q0 != q. Takze to, ze by prijmal JEN prazdne slovo, neni vylouceno. Kdyz me nekdo opravi, budu rad. Dik.
Uživatelský avatar
Hans
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 20. 12. 2007 20:07
Typ studia: Informatika Bc.
Bydliště: Jižák
Kontaktovat uživatele:

Re: Testové otázky - aktualizovaná verze

Příspěvek od Hans »

zvedavec obecny píše:Otazka 13: Ja myslim, ze L muze byt prazdny. Nikde neni omezeno, ze w != lambda nebo q0 != q. Takze to, ze by prijmal JEN prazdne slovo, neni vylouceno. Kdyz me nekdo opravi, budu rad. Dik.
Jenže musíš rozlišit dvě věci 1. L = prázdný jazyk, 2. L = { lambda } - jazyk obsahující prázdné slovo :wink:
marxin
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 30. 1. 2008 13:24
Typ studia: Informatika Mgr.

Re: Testové otázky - aktualizovaná verze

Příspěvek od marxin »

Přesně jak napsal Hans, otázka je dobře a není třeba ji opravovat ;)
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: Testové otázky - aktualizovaná verze

Příspěvek od Donarus »

ot.5:

tohle je prece blbost, ze 0^n1^n je podmnozinou (01)*, neni-liz pravda ??podmnozinou (01)* je tak maximalne {0^0.1^0,0^1.1^1} a to regularni preci je ... ??mozna kdyby zduvodneni bylo (0*.1*) a pak podmnozina 0^n.1^n -> pak bych tomu veril...

ale vyvedte me z omylo :) :D



ot.23:

proc by nemelo platit c ?? pokud to dobre chapu z tech posahanejch slidu (a s mym spankovym deficitem), tak preci kdyz "q je z F", tak plati i "q je (jednoprvkovou) podmnozinou F"
Uživatelský avatar
Hans
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 20. 12. 2007 20:07
Typ studia: Informatika Bc.
Bydliště: Jižák
Kontaktovat uživatele:

Re: Testové otázky - aktualizovaná verze

Příspěvek od Hans »

U otázky 5 je asi zdůvodnění špatně napsané, každopádně je to myšleno tak, že jazyk, který vznikne libovolnou kombinací 0 a 1 je regulární (KA : 1 stav, který je zároveň vstupní a výstupní a pro 0 i 1 vede přechod zpět do tohoto stavu) a jazyk 0^n1^n, který je evidentně podmnožinou tohoto jazyka, regulární není

U otázky 23 je potřeba rozlišovat mezi relací náležet do (prvek náleží do množiny prvků) a býti podmnožinou (množina prvků je podmnožinou množiny prvků). Aby platilo c, muselo by být napsáno {q} \subseteq F, kde q je koncový stav.
Šlupka
Matfyz(ák|ačka) level I
Příspěvky: 39
Registrován: 7. 11. 2007 22:12
Typ studia: Informatika Bc.

Re: Testové otázky - aktualizovaná verze

Příspěvek od Šlupka »

Donarus píše:ot.5:

tohle je prece blbost, ze 0^n1^n je podmnozinou (01)*, neni-liz pravda ??podmnozinou (01)* je tak maximalne {0^0.1^0,0^1.1^1} a to regularni preci je ... ??mozna kdyby zduvodneni bylo (0*.1*) a pak podmnozina 0^n.1^n -> pak bych tomu veril...

ale vyvedte me z omylo :) :D
Argument stačí trošku poopravit. Místo (01)* dej (0+1)* a máš to :D
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: Testové otázky - aktualizovaná verze

Příspěvek od Donarus »

no to vim, ze to takhle plati, jen jsem si rikal, zestli v te ranni hodine neco neprehlizim, ale vidim, ze ne ... :)
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: Testové otázky - aktualizovaná verze

Příspěvek od Donarus »

Hans píše:U otázky 5 je asi zdůvodnění špatně napsané, každopádně je to myšleno tak, že jazyk, který vznikne libovolnou kombinací 0 a 1 je regulární (KA : 1 stav, který je zároveň vstupní a výstupní a pro 0 i 1 vede přechod zpět do tohoto stavu) a jazyk 0^n1^n, který je evidentně podmnožinou tohoto jazyka, regulární není

U otázky 23 je potřeba rozlišovat mezi relací náležet do (prvek náleží do množiny prvků) a býti podmnožinou (množina prvků je podmnožinou množiny prvků). Aby platilo c, muselo by být napsáno {q} \subseteq F, kde q je koncový stav.
me to taky docvaklo ted rano, ze to bude zas jeden prehlidnutej dulezitej detail, kteryho bych si mohl uz nekolik let, aspon co jsem na skole, vsinmout i o pulnoci kdyz me nekdo vzbudi - kdyz ono bylo uz po pulnoci, tak me to snad omlouva :) :)
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Testové otázky - aktualizovaná verze

Příspěvek od Him »

Proc u ot. 45 neni spravnou odpovedi i B? Mate nekdo protipriklad?

Napadlo me: Mame automat A, ktery je treba redukovany. Mame automat B, ktery je treba take redukovany (tahle cast je ekv. s A) a obsahuje navic nedosazitelne stavy (graf automatu B se rozpadne na dve komponenty). Pak automaty jsou ekvivalentni, ale neni mezi nimi homomorfismus -- nejak takto?
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Návštěvník

Re: Testové otázky - aktualizovaná verze

Příspěvek od Návštěvník »

rekl bych, ze B neplati, protoze veta ktera se zminuje o ekvivalenci a homomorfismu je pouze implikace...a tvuj protipriklad je podle me spravny, akorat automat, ktery je redukovany, nemuze obsahovat nedosazitelne stavy, takze automat B nemuze byt redukovany...
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Testové otázky - aktualizovaná verze

Příspěvek od Him »

Guest: U B je redukovana jen ta dosazitelna cast.. je to nepresne napsane, ale myslel jsem to dobre :))
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
H8me

Re: Testové otázky - aktualizovaná verze

Příspěvek od H8me »

Ahojte,
tie linky uz nefunguju, nenasiel by sa niekto kto to ma a bol by to ochotny to sem postnut ? :]

Dik.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Testové otázky - aktualizovaná verze

Příspěvek od Him »

Doufam, ze toto je spravna verze tech souboru - rozdily oproti puvodni verzi nebyly az tak velke.
Přílohy
2cast_resene.pdf
(113.46 KiB) Staženo 878 x
2cast_resene.doc
(88 KiB) Staženo 317 x
1cast_resene.pdf
(231.41 KiB) Staženo 7173 x
1cast_resene.doc
(383 KiB) Staženo 328 x
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
bujon
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 28. 1. 2007 12:22

Re: Testové otázky - aktualizovaná verze

Příspěvek od bujon »

Doufam ze to je ono co tu bylo ke stahnuti na zacatku.
Přílohy
1cast_resene_verze2.pdf
(517.16 KiB) Staženo 978 x
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“