Otazky
-
- Matfyz(ák|ačka) level I
- Příspěvky: 2
- Registrován: 3. 2. 2007 12:25
Otazky
Tady mate vyfocene otazky s pravdepodobne (nerucim!) spravnymi odpovedmi. Na druhem pokusu byly skoro stejne, tak doufejte, ze ani dal se nebudou moc menit...
http://matfyz.cskd.cz
http://matfyz.cskd.cz
Naposledy upravil(a) ngsoftware dne 21. 1. 2008 03:09, celkem upraveno 1 x.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 13
- Registrován: 24. 1. 2006 15:15
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Zdravim,
chcem sa opytat, ze ci v otazke :
Necht G = (N,T,S,P) je monotonni generativni gramatika a (u→v)∈P je jeji pravidlo. Potom plati:
- |u| ≤ |v|
- |v| ≤ |u|
- u = αβγ, α,γ∈(N∪T)*, β∈N
- v = αβγ, α,γ∈(N∪T)*, β∈N
nema byt spravne zaskrtnuta aj moznost a).
Lebo z definicie monotonnej gram mi to tak docela vyplyva. Len neviem, co to je generativna gramatika. Tak sa mozno mylim.
chcem sa opytat, ze ci v otazke :
Necht G = (N,T,S,P) je monotonni generativni gramatika a (u→v)∈P je jeji pravidlo. Potom plati:
- |u| ≤ |v|
- |v| ≤ |u|
- u = αβγ, α,γ∈(N∪T)*, β∈N
- v = αβγ, α,γ∈(N∪T)*, β∈N
nema byt spravne zaskrtnuta aj moznost a).
Lebo z definicie monotonnej gram mi to tak docela vyplyva. Len neviem, co to je generativna gramatika. Tak sa mozno mylim.
Naposledy upravil(a) strky dne 25. 6. 2007 23:40, celkem upraveno 1 x.
- Lukas Mach
- Matfyz(ák|ačka) level III
- Příspěvky: 261
- Registrován: 28. 3. 2006 17:08
- Typ studia: Informatika Bc.
- Bydliště: Praha a Kladno
- Kontaktovat uživatele:
Protoze je nedeterministicky a jednim slovem se muzes dostat napriklad do dvou stavu q<sub>1</sub> a q<sub>2</sub>. Kdyz se stane, ze q<sub>1</sub>∈F a zaroven plati, ze q<sub>2</sub>∉F, tak to slovo bude i v druhem automatu.cathack píše:Něco mi asi uniká, ale proč prosím neplatí ve druhé otázce z druhé stránky možnost, že automat s koncovými stavy Q-F přijímá jazyk X*-L(A)?
For every epsilon, there is delta.
Where is my delta?
Where is my delta?
- cathack
- Matfyz(ák|ačka) level I
- Příspěvky: 31
- Registrován: 31. 1. 2006 14:18
- Typ studia: Informatika Bc.
- Login do SIS: kubit5am
Jasně, díky. Aby to totiž platilo, musel by být automat deterministický.Lukas Mach píše:Protoze je nedeterministicky a jednim slovem se muzes dostat napriklad do dvou stavu q1 a q2. Kdyz se stane, ze q1 `elementem` F a zaroven plati, ze q2 not `elementem` F, tak to slovo bude i v druhem automatu.cathack píše:Něco mi asi uniká, ale proč prosím neplatí ve druhé otázce z druhé stránky možnost, že automat s koncovými stavy Q-F přijímá jazyk X*-L(A)?
Ještě jsem se zastavil u otázky následující po této. Je to automat s obrázkem. Nechápu moc zadání a už vůbec ne výsledek
Chápu to tak, že pro nějaké přijímané slovo provedu výpočet a ve druhém kroku (po druhém přečteném písmenu) se kouknu v jakých jsem stavech. Odpovědět mám jaké všechny možné stavy to můžou být.Nechť máme daný následující automat A. (obrázek) Do jakých stavů se tento automat může dostat v přijímajícím výpočtu nějakého slova z jazyka L(A) po přečtení prvních dvou písmen?
Pak by ale byl správně i stav B. Např. pro slovo "bba" jsou stavy v jednotlivých krocích AD->BD->BD->A. Stav A je výstupní a ve druhém kroku jsem i ve stavu B. Zřejmě mám někde chybu v interpretaci zadání. Poradí mi prosím někdo?
- Lukas Mach
- Matfyz(ák|ačka) level III
- Příspěvky: 261
- Registrován: 28. 3. 2006 17:08
- Typ studia: Informatika Bc.
- Bydliště: Praha a Kladno
- Kontaktovat uživatele:
B je mrtvy stav - jakmile se do nej dostanes, uz nemuze byt to slovo elementem L(A), cili do stavu B se nemuzes dostat prijimacim vypoctem.cathack píše:Chápu to tak, že pro nějaké přijímané slovo provedu výpočet a ve druhém kroku (po druhém přečteném písmenu) se kouknu v jakých jsem stavech. Odpovědět mám jaké všechny možné stavy to můžou být.
Pak by ale byl správně i stav B. Např. pro slovo "bba" jsou stavy v jednotlivých krocích AD->BD->BD->A. Stav A je výstupní a ve druhém kroku jsem i ve stavu B. Zřejmě mám někde chybu v interpretaci zadání. Poradí mi prosím někdo?
For every epsilon, there is delta.
Where is my delta?
Where is my delta?
-
- Matfyz(ák|ačka) level I
- Příspěvky: 49
- Registrován: 2. 2. 2006 15:58
problem je v definici te otazky, viz moje reseni k dalsi varinate: http://forum.matfyz.info/viewtopic.php?t=3416
rozlisuje tam varinaty, kdy jde o slovo, ktere je prijato (stav kam se dostanu prectenim toho slova musi byt koncoy stav) a kdy je slovo jen precteno (stav do ktereho se prectenim toho slova dostanu muze byt jakykoliv).
Proste precteno neznamena prijato to je ta oskliva finticka
rozlisuje tam varinaty, kdy jde o slovo, ktere je prijato (stav kam se dostanu prectenim toho slova musi byt koncoy stav) a kdy je slovo jen precteno (stav do ktereho se prectenim toho slova dostanu muze byt jakykoliv).
Proste precteno neznamena prijato to je ta oskliva finticka
Automaty a Gramatiky
Rozhodne ano, vsak priamo z definicie monotonnej gramatiky. Obecne v tych testoch nie su vsetky otazky odpovedane celkom koser, takze treba zapojit aj vlastnu hlavustrky píše:Zdravim,
chcem sa opytat, ze ci v otazke :
Necht G = (N,T,S,P) je monotonni generativni gramatika a (u→v)∈P je jeji pravidlo. Potom plati:
- |u| ≤ |v|
- |v| ≤ |u|
- u = αβγ, α,γ∈(N∪T)*, β∈N
- v = αβγ, α,γ∈(N∪T)*, β∈N
nema byt spravne zaskrtnuta aj moznost a).
Lebo z definicie monotonnej gram mi to tak docela vyplyva. Len neviem, co to je generativna gramatika. Tak sa mozno mylim.
- stnicolaus
- Matfyz(ák|ačka) level II
- Příspěvky: 73
- Registrován: 22. 1. 2006 17:39
- Typ studia: Informatika Bc.
- Login do SIS: matal4am
- Bydliště: Plzeň
- Kontaktovat uživatele:
Re: Otazky
Nemá být u druhé otázky na třetí stránce správná odpověď A (místo vyznačeného B)?
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 10. 12. 2004 22:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: Otazky
Nie, vsimni si podmnozinovej relacie u delta.stnicolaus píše:Nemá být u druhé otázky na třetí stránce správná odpověď A (místo vyznačeného B)?
//edit
Teda dufam
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
- stnicolaus
- Matfyz(ák|ačka) level II
- Příspěvky: 73
- Registrován: 22. 1. 2006 17:39
- Typ studia: Informatika Bc.
- Login do SIS: matal4am
- Bydliště: Plzeň
- Kontaktovat uživatele:
Re: Otazky
To je podle mne jedno. Kdyby to byl nedeterministický automat, mohl by mít víc než jeden počáteční vrchol a ta delta, by byla QxXxP(Q) (z jednoho vrcholu může vést na stejné písmenko víc hran).MIKI píše:Nie, vsimni si podmnozinovej relacie u delta.stnicolaus píše:Nemá být u druhé otázky na třetí stránce správná odpověď A (místo vyznačeného B)?
//edit
Teda dufam
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Otazky
Ne, tam je to dobře. Deterministický automat to být nemůže, zkusme zvolit za delta prázdnou množinu, pak je to nedeterministický automat. Ten zásobníkový automat je už úplně špatně. Takže jediná správná odpověď je vskutku b.stnicolaus píše:To je podle mne jedno. Kdyby to byl nedeterministický automat, mohl by mít víc než jeden počáteční vrchol a ta delta, by byla QxXxP(Q) (z jednoho vrcholu může vést na stejné písmenko víc hran).MIKI píše:Nie, vsimni si podmnozinovej relacie u delta.stnicolaus píše:Nemá být u druhé otázky na třetí stránce správná odpověď A (místo vyznačeného B)?
//edit
Teda dufam
Tady jde o to, že ne každý nedeterministický automat má více počátečních vrcholů, a zde se neptají, zda každý NDKA vypadá takhle.
Osiris
- stnicolaus
- Matfyz(ák|ačka) level II
- Příspěvky: 73
- Registrován: 22. 1. 2006 17:39
- Typ studia: Informatika Bc.
- Login do SIS: matal4am
- Bydliště: Plzeň
- Kontaktovat uživatele:
Re: Otazky
Teď už jsem to pochopil - díkyOsiris píše:Ne, tam je to dobře. Deterministický automat to být nemůže, zkusme zvolit za delta prázdnou množinu, pak je to nedeterministický automat. Ten zásobníkový automat je už úplně špatně. Takže jediná správná odpověď je vskutku b.stnicolaus píše: To je podle mne jedno. Kdyby to byl nedeterministický automat, mohl by mít víc než jeden počáteční vrchol a ta delta, by byla QxXxP(Q) (z jednoho vrcholu může vést na stejné písmenko víc hran).
Tady jde o to, že ne každý nedeterministický automat má více počátečních vrcholů, a zde se neptají, zda každý NDKA vypadá takhle.
Re: Otazky
Ja bych mel taky jeden dotaz... proc na 2. obrazku predposledni otazce je spravne pouze 1. tvrzeni? Proc nejde i 3. moznost?