od Acris » 30. 5. 2010 09:48
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 0
n 1
m pro 0<n<=m je deterministický bezkontextový, dá se přijmout deterministickým zásobníkovým automatem, ale není bezprefixový (Např. 0
n 1
n je prefixem slova 0
n 1
n+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í.
[quote="steves"][quote="peci1"][quote="bujon"]Mne neni jasna jeste otazka 6. Spravne odpovedi jsou CD? Tedy ze prijimany jazyk je bezkontextovy a zaroven kontextovy? To jde?[/quote]
hn odpovedel spravne... Navic je tam podstatne, ze otazka zni: "jazyky ... jsou vzdycky ..." a ne "jazyky ... jsou prave ..."[/quote]
Mně to pořád nějak nehraje. Otázka zní: "Jazyk, ktery prijima [b]deterministicky[/b] zasobnikovy automat koncovym stavem je vzdy:" a odpověď by podle mě měla být [b]deterministický[/b] 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é(?)[/quote]
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 0[sup]n[/sup] 1[sup]m[/sup] pro 0<n<=m je deterministický bezkontextový, dá se přijmout deterministickým zásobníkovým automatem, ale není bezprefixový (Např. 0[sup]n[/sup] 1[sup]n[/sup] je prefixem slova 0[sup]n[/sup] 1[sup]n+1[/sup]). 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í.