Otazky

[ngsoftware]

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

[themish]

to je super! dik moc!

[strky]

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.

[cathack]

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)?

[Lukas Mach]

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)?

Protoze je nedeterministicky a jednim slovem se muzes dostat napriklad do dvou stavu q₁ a q₂. Kdyz se stane, ze q₁∈F a zaroven plati, ze q₂∉F, tak to slovo bude i v druhem automatu.

[cathack]

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)?

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.

Jasně, díky. Aby to totiž platilo, musel by být automat deterministický.

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

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?

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?

[Lukas Mach]

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?

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.

[Ošklivý sup]

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

[oskEE]

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.

Rozhodne ano, vsak priamo z definicie monotonnej gramatiky. Obecne v tych testoch nie su vsetky otazky odpovedane celkom koser, takze treba zapojit aj vlastnu hlavu

[stnicolaus]

Nemá být u druhé otázky na třetí stránce správná odpověď A (místo vyznačeného B)?

[MIKI]

Nemá být u druhé otázky na třetí stránce správná odpověď A (místo vyznačeného B)?

Nie, vsimni si podmnozinovej relacie u delta.
//edit
Teda dufam

[stnicolaus]

Nemá být u druhé otázky na třetí stránce správná odpověď A (místo vyznačeného B)?

Nie, vsimni si podmnozinovej relacie u delta.
//edit
Teda dufam

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

[Osiris]

Nemá být u druhé otázky na třetí stránce správná odpověď A (místo vyznačeného B)?

Nie, vsimni si podmnozinovej relacie u delta.
//edit
Teda dufam

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

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.

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.

[stnicolaus]

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

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.

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.

Teď už jsem to pochopil - díky

[Newton122]

Ja bych mel taky jeden dotaz... proc na 2. obrazku predposledni otazce je spravne pouze 1. tvrzeni? Proc nejde i 3. moznost?