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

Mne neni jasna jeste otazka 6. Spravne odpovedi jsou CD? Tedy ze prijimany jazyk je bezkontextovy a zaroven kontextovy? To jde?
hn

Re: Testové otázky - aktualizovaná verze

Příspěvek od hn »

no ved bezkontextove jazyky tvoria podmnozinu kontextovych nie?
peci1
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

Příspěvek od peci1 »

bujon píše:Mne neni jasna jeste otazka 6. Spravne odpovedi jsou CD? Tedy ze prijimany jazyk je bezkontextovy a zaroven kontextovy? To jde?
hn odpovedel spravne... Navic je tam podstatne, ze otazka zni: "jazyky ... jsou vzdycky ..." a ne "jazyky ... jsou prave ..."
steves
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

Příspěvek od steves »

peci1 píše:
bujon píše:Mne neni jasna jeste otazka 6. Spravne odpovedi jsou CD? Tedy ze prijimany jazyk je bezkontextovy a zaroven kontextovy? To jde?
hn odpovedel spravne... Navic je tam podstatne, ze otazka zni: "jazyky ... jsou vzdycky ..." a ne "jazyky ... jsou prave ..."
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.

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é(?)
Acris
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

Příspěvek od Acris »

steves píše:
peci1 píše:
bujon píše:Mne neni jasna jeste otazka 6. Spravne odpovedi jsou CD? Tedy ze prijimany jazyk je bezkontextovy a zaroven kontextovy? To jde?
hn odpovedel spravne... Navic je tam podstatne, ze otazka zni: "jazyky ... jsou vzdycky ..." a ne "jazyky ... jsou prave ..."
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.

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é(?)
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ěď.

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í.
Pitr2311
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 3. 9. 2009 17:54
Typ studia: Informatika Mgr.

Re: Testové otázky - aktualizovaná verze

Příspěvek od Pitr2311 »

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ě"(?)
...
Ak jazyk, ktory prijima automat, patri do nejakej triedy, urcite patri aj do vsetkyc NADMNOZIN tej triedy, nie PODMNOZIN, ako pises... ;)

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)
Snad som ta tym nezamotal este viac, ak ano, mozes tento prispevok ignorovat ;)
Pitr2311
peci1
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

Příspěvek od peci1 »

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 ;)
marion
Matfyz(ák|ačka) level II
Příspěvky: 69
Registrován: 4. 10. 2008 11:05
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Testové otázky - aktualizovaná verze

Příspěvek od marion »

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á?
Pitr2311
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 3. 9. 2009 17:54
Typ studia: Informatika Mgr.

Re: Testové otázky - aktualizovaná verze

Příspěvek od Pitr2311 »

marion 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á?
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)=L
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
1.John
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 18. 2. 2010 16:10
Typ studia: Informatika Bc.

Re: Testové otázky - aktualizovaná verze

Příspěvek od 1.John »

7 je odpověď A (část 1)
1.John
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 18. 2. 2010 16:10
Typ studia: Informatika Bc.

Re: Testové otázky - aktualizovaná verze

Příspěvek od 1.John »

24:
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.)
nema to byt tedy nadmnozina?
Premun
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

Příspěvek od Premun »

1.John píše:24:
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.)
nema to byt tedy nadmnozina?
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.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“