Testové otázky - aktualizovaná verze
Re: Testové otázky - aktualizovaná verze
Mne neni jasna jeste otazka 6. Spravne odpovedi jsou CD? Tedy ze prijimany jazyk je bezkontextovy a zaroven kontextovy? To jde?
Re: Testové otázky - aktualizovaná verze
no ved bezkontextove jazyky tvoria podmnozinu kontextovych nie?
-
- Matfyz(ák|ačka) level II
- Příspěvky: 86
- Registrován: 21. 1. 2009 20:08
- Typ studia: Informatika Bc.
Re: Testové otázky - aktualizovaná verze
hn odpovedel spravne... Navic je tam podstatne, ze otazka zni: "jazyky ... jsou vzdycky ..." a ne "jazyky ... jsou prave ..."bujon píše:Mne neni jasna jeste otazka 6. Spravne odpovedi jsou CD? Tedy ze prijimany jazyk je bezkontextovy a zaroven kontextovy? To jde?
-
- Matfyz(ák|ačka) level I
- Příspěvky: 33
- Registrován: 13. 12. 2008 16:29
- Typ studia: Informatika Bc.
Re: Testové otázky - aktualizovaná verze
Mně to pořád nějak nehraje. Otázka zní: "Jazyk, ktery prijima deterministicky zasobnikovy automat koncovym stavem je vzdy:" a odpověď by podle mě měla být deterministický bezkontextový jazyk, viz přehled jazyků a automatů k nim příslušným na slajdech "lecture09". Bezkontextove ("nedeterministické") jazyky jsou, podle slajdů, přijímány (nedeterministickým) zásobníkovým automatem.peci1 píše:hn odpovedel spravne... Navic je tam podstatne, ze otazka zni: "jazyky ... jsou vzdycky ..." a ne "jazyky ... jsou prave ..."bujon píše:Mne neni jasna jeste otazka 6. Spravne odpovedi jsou CD? Tedy ze prijimany jazyk je bezkontextovy a zaroven kontextovy? To jde?
Navíc, podle tvojí logiky, by správnou odpovědí mělo být i za a), tedy regulární jazyk, protože regulární jazyky jsou podmnožinou bezkontextových, i za b) bezprefixový jazyk ze stejného důvodu... Podle mě to "jsou vždy" znamená to samé jako "jsou právě"(?)
Ovšem potom by nebyla správná odpověď žádná, což je asi možné, ale nevím, jak pravděpodobné(?)
-
- Matfyz(ák|ačka) level I
- Příspěvky: 20
- Registrován: 26. 1. 2010 14:28
- Typ studia: Informatika Mgr.
- Bydliště: Praha
Re: Testové otázky - aktualizovaná verze
Jazyk, který přijímá deterministický zásobníkový automat koncovým stavem je vždy deterministický bezkontextový jazyk. Každý takovýto jazyk je bezkontextový. A každý bezkontextový jazyk splňuje i pravidla kontextového jazyka, tedy je i vždy kontextový. Tedy CD je opravdu správná odpověď.steves píše:Mně to pořád nějak nehraje. Otázka zní: "Jazyk, ktery prijima deterministicky zasobnikovy automat koncovym stavem je vzdy:" a odpověď by podle mě měla být deterministický bezkontextový jazyk, viz přehled jazyků a automatů k nim příslušným na slajdech "lecture09". Bezkontextove ("nedeterministické") jazyky jsou, podle slajdů, přijímány (nedeterministickým) zásobníkovým automatem.peci1 píše:hn odpovedel spravne... Navic je tam podstatne, ze otazka zni: "jazyky ... jsou vzdycky ..." a ne "jazyky ... jsou prave ..."bujon píše:Mne neni jasna jeste otazka 6. Spravne odpovedi jsou CD? Tedy ze prijimany jazyk je bezkontextovy a zaroven kontextovy? To jde?
Navíc, podle tvojí logiky, by správnou odpovědí mělo být i za a), tedy regulární jazyk, protože regulární jazyky jsou podmnožinou bezkontextových, i za b) bezprefixový jazyk ze stejného důvodu... Podle mě to "jsou vždy" znamená to samé jako "jsou právě"(?)
Ovšem potom by nebyla správná odpověď žádná, což je asi možné, ale nevím, jak pravděpodobné(?)
Naopak bezprefixový být nemusí. Jazyk 0n 1m pro 0<n<=m je deterministický bezkontextový, dá se přijmout deterministickým zásobníkovým automatem, ale není bezprefixový (Např. 0n 1n je prefixem slova 0n 1n+1). A není ani regulární. (Např. důkaz Nerodem.)
Tedy jazyk přijímaný tímto automatem nemusí být vždy bezprefixový ani regulární.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 3. 9. 2009 17:54
- Typ studia: Informatika Mgr.
- Login do SIS: 78761606
Re: Testové otázky - aktualizovaná verze
Ak jazyk, ktory prijima automat, patri do nejakej triedy, urcite patri aj do vsetkyc NADMNOZIN tej triedy, nie PODMNOZIN, ako pises...steves píše:...
Navíc, podle tvojí logiky, by správnou odpovědí mělo být i za a), tedy regulární jazyk, protože regulární jazyky jsou podmnožinou bezkontextových, i za b) bezprefixový jazyk ze stejného důvodu... Podle mě to "jsou vždy" znamená to samé jako "jsou právě"(?)
...
Rozdiel medzi "jsou vzdy" a "jsou prave" je:
- "jsou vzdy" znamena implikaciu: L je jazyk rozpoznatelny niektorym typom automatu, potom L patri urcitej triede (netvrdi ze kazdy jazyk z tej danej triedy je rozpoznatelny spominanym typom automatu)
- "jsou prave" znamena ekvivalenciu: L je jazyk rozpoznatelny niektorym typom automatu, prave ked L patri urcitej triede (teda mnozina jazykov rozpoznatelnych tymto typom automatov je rovna prave konkretnej triede jazykov)
Pitr2311
-
- Matfyz(ák|ačka) level II
- Příspěvky: 86
- Registrován: 21. 1. 2009 20:08
- Typ studia: Informatika Bc.
Re: Testové otázky - aktualizovaná verze
Ahoj, ted koukam na otazku 8. ("prunik" automatu, ale misto F1xF2 mame Q1xQ2).
Jen chci pridat zduvodneni, proc C (ze prijima X*) je spravne, protoze mne to na chvili zmatlo a myslel jsem si, ze ani tahle odpoved neni spravna.
Muj protiargument byl takovy, ze kdybych mel automat nad abecedou {a, b}, ale automat obsahoval jen prechody pro a, pak by slova s becky vubec ve vysledku nebyla. Jenze. Jde o deterministicke automaty, tedy je nemuzu "utnout" tak jako NKA, a tedy pro kazdy stav a pismeno MUSIM mit definovanou prechodovou funkci. Coz mimo jine znamena, ze na libovlnem slovu ten automat bude porad prebihat mezi svymi stavy. A ty jsou vsechny koncove, takze opravdu prijme kazde slovo.
Good luck
Jen chci pridat zduvodneni, proc C (ze prijima X*) je spravne, protoze mne to na chvili zmatlo a myslel jsem si, ze ani tahle odpoved neni spravna.
Muj protiargument byl takovy, ze kdybych mel automat nad abecedou {a, b}, ale automat obsahoval jen prechody pro a, pak by slova s becky vubec ve vysledku nebyla. Jenze. Jde o deterministicke automaty, tedy je nemuzu "utnout" tak jako NKA, a tedy pro kazdy stav a pismeno MUSIM mit definovanou prechodovou funkci. Coz mimo jine znamena, ze na libovlnem slovu ten automat bude porad prebihat mezi svymi stavy. A ty jsou vsechny koncove, takze opravdu prijme kazde slovo.
Good luck
-
- Matfyz(ák|ačka) level II
- Příspěvky: 69
- Registrován: 4. 10. 2008 11:05
- Typ studia: Informatika Mgr.
- Login do SIS: 36138549
- Kontaktovat uživatele:
Re: Testové otázky - aktualizovaná verze
Ot. č. 8: jestliže všechny stavy jsou koncové, chápu, že správná odpověď je c) X*. Proč ale nejsou správné všechny odpovědi, neboť myslím, že všechny ostatní jazyky jsou podmnožinou X* a automat je přijímá taky. Nebo mi něco uniká?
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 3. 9. 2009 17:54
- Typ studia: Informatika Mgr.
- Login do SIS: 78761606
Re: Testové otázky - aktualizovaná verze
Podla mojho nazoru, "Automat A prijima jazyk L" znamena, ze mnozina slov, ktore koncia v nejakom koncovom stave A (=L(A)) je prave mnozina slov v danom jazyku L, teda L(A)=Lmarion píše:Ot. č. 8: jestliže všechny stavy jsou koncové, chápu, že správná odpověď je c) X*. Proč ale nejsou správné všechny odpovědi, neboť myslím, že všechny ostatní jazyky jsou podmnožinou X* a automat je přijímá taky. Nebo mi něco uniká?
Potom jednoducho konkretny automat prijima prave jeden jazyk, pri jeho podmnozinach by sa mohlo stat, ze slovo je prijate automatom, ale nie je v danom "prijimanom" jazyku
Dufam, ze moja predstava je spravna
Pitr2311
-
- Matfyz(ák|ačka) level I
- Příspěvky: 10
- Registrován: 18. 2. 2010 16:10
- Typ studia: Informatika Bc.
- Login do SIS: Alien
Re: Testové otázky - aktualizovaná verze
7 je odpověď A (část 1)
-
- Matfyz(ák|ačka) level I
- Příspěvky: 10
- Registrován: 18. 2. 2010 16:10
- Typ studia: Informatika Bc.
- Login do SIS: Alien
Re: Testové otázky - aktualizovaná verze
24:
nema to byt tedy nadmnozina?Nechť máme nedeterministický konečný automat A s jediným počátečním stavem q0, s koncovými stavy F,
přechodovou funkci a u je libovolné slovo z jazyka L(A). Potom platí:
[ ] *(q0,u)=F
[ ] *(q0,u) in F
[ ] *(q0,u) podmnozina F
[ ] *(q0,u) nadmozina F
Odpověď:
nic (Tím že je nedeterministický se s jednim slovem muzeme dostat do dvou stavu, z kterych napr. jen jeden ze z F.)
-
- Matfyz(ák|ačka) level I
- Příspěvky: 7
- Registrován: 6. 6. 2011 22:52
- Typ studia: Informatika Mgr.
Re: Testové otázky - aktualizovaná verze
Tím že je nedeterministický se s jednim slovem muzeme dostat do dvou stavu, z kterych napr. jen jeden ze z F.1.John píše:24:nema to byt tedy nadmnozina?Nechť máme nedeterministický konečný automat A s jediným počátečním stavem q0, s koncovými stavy F,
přechodovou funkci a u je libovolné slovo z jazyka L(A). Potom platí:
[ ] *(q0,u)=F
[ ] *(q0,u) in F
[ ] *(q0,u) podmnozina F
[ ] *(q0,u) nadmozina F
Odpověď:
nic (Tím že je nedeterministický se s jednim slovem muzeme dostat do dvou stavu, z kterych napr. jen jeden ze z F.)
Tzn.
Q = {a,b,c}
F = {a,c}
a nedeterministicky vypocty skonci v {a,b} - slovo je prijato (kvuli a), ale neni to podmnozina a ani nadmnozina F.