Otazky

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).
ngsoftware
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 3. 2. 2007 12:25

Otazky

Příspěvek od 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... 8)

http://matfyz.cskd.cz
Naposledy upravil(a) ngsoftware dne 21. 1. 2008 03:09, celkem upraveno 1 x.
Uživatelský avatar
themish
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 31. 1. 2006 21:52
Typ studia: Informatika Bc.
Bydliště: skoro prahaa
Kontaktovat uživatele:

diik

Příspěvek od themish »

to je super! :) dik moc!
Jsem člověk, který se nezdá. Například jednou jsem se vůbec nezdál, a přece!
strky
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 24. 1. 2006 15:15
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od 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.
Naposledy upravil(a) strky dne 25. 6. 2007 22:40, celkem upraveno 1 x.
Uživatelský avatar
cathack
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 31. 1. 2006 14:18
Typ studia: Informatika Bc.

Příspěvek od 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)?
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 16:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Příspěvek od Lukas Mach »

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)?
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.
For every epsilon, there is delta.
Where is my delta?
Uživatelský avatar
cathack
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 31. 1. 2006 14:18
Typ studia: Informatika Bc.

Příspěvek od cathack »

Lukas Mach píše:
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)?
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?
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 16:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Příspěvek od Lukas Mach »

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?
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.
For every epsilon, there is delta.
Where is my delta?
Ošklivý sup
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 2. 2. 2006 15:58

Příspěvek od 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

Automaty a Gramatiky

Příspěvek od oskEE »

strky 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.
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 ;)
Uživatelský avatar
stnicolaus
Matfyz(ák|ačka) level II
Příspěvky: 73
Registrován: 22. 1. 2006 17:39
Typ studia: Informatika Bc.
Bydliště: Plzeň
Kontaktovat uživatele:

Re: Otazky

Příspěvek od stnicolaus »

Nemá být u druhé otázky na třetí stránce správná odpověď A (místo vyznačeného B)?
MIKI
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

Příspěvek od MIKI »

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)?
Nie, vsimni si podmnozinovej relacie u delta.
//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ť.
Uživatelský avatar
stnicolaus
Matfyz(ák|ačka) level II
Příspěvky: 73
Registrován: 22. 1. 2006 17:39
Typ studia: Informatika Bc.
Bydliště: Plzeň
Kontaktovat uživatele:

Re: Otazky

Příspěvek od stnicolaus »

MIKI píše:
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)?
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
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

Příspěvek od Osiris »

stnicolaus píše:
MIKI píše:
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)?
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.
Osiris
Uživatelský avatar
stnicolaus
Matfyz(ák|ačka) level II
Příspěvky: 73
Registrován: 22. 1. 2006 17:39
Typ studia: Informatika Bc.
Bydliště: Plzeň
Kontaktovat uživatele:

Re: Otazky

Příspěvek od stnicolaus »

Osiris píše:
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).
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 :wink:
Newton122

Re: Otazky

Příspěvek od Newton122 »

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

Zpět na „TIN071 Automaty a gramatiky“