Zkouška 14.06.2006
-
- Matfyz(ák|ačka) level III
- Příspěvky: 103
- Registrován: 4. 6. 2005 15:49
- Typ studia: Informatika Bc.
- Bydliště: Vyšehrad
Zkouška 14.06.2006
Tak až na malé nuance v zadání automatů a gramatik (spíše v jednodušším směru), jako vždy..
- Almer
- Site Admin
- Příspěvky: 686
- Registrován: 12. 10. 2004 10:58
- Typ studia: Informatika Ph.D.
- Login do SIS: lasap4am
- Bydliště: Mala Strana - 203
- Kontaktovat uživatele:
povrzuji...dostal jsem variantu A..
JInak, docela dlouze jsem resil , co s prikladem 10 (ten skoro pumping lemma).
Mno, vzhledem k tomu , ze |z| >= p a |w|<= p tedy vime, ze |z| >= |w|. Protoze z = u v w a v neni lambda, tudiz vime, ze |z| > |w| nebot |v|>=1. Vezmeme tedy slovo delky rovny p. Tedy takove slovo ma |v| aspom 1 a |w| maximalne p-1. vezmu li tedy maximalni slovo, tedy |u| = 0 a pumpuju dolu. Tedy mam slovo pouze z= v^0 w prvkem L, coz je ale spor s tim, ze |z|>=p.
TAKTO jsem se to snazil umlatit. CO je na tom spatne?
JInak, docela dlouze jsem resil , co s prikladem 10 (ten skoro pumping lemma).
Mno, vzhledem k tomu , ze |z| >= p a |w|<= p tedy vime, ze |z| >= |w|. Protoze z = u v w a v neni lambda, tudiz vime, ze |z| > |w| nebot |v|>=1. Vezmeme tedy slovo delky rovny p. Tedy takove slovo ma |v| aspom 1 a |w| maximalne p-1. vezmu li tedy maximalni slovo, tedy |u| = 0 a pumpuju dolu. Tedy mam slovo pouze z= v^0 w prvkem L, coz je ale spor s tim, ze |z|>=p.
TAKTO jsem se to snazil umlatit. CO je na tom spatne?
Zakládající člen klubu Ortodoxních Matfyzáků
Jsem LAMER ale neumim se ani podepsat ]
Jsem LAMER ale neumim se ani podepsat ]
- Dawe
- Supermatfyz(ák|ačka)
- Příspěvky: 360
- Registrován: 12. 10. 2004 12:32
- Typ studia: Informatika Mgr.
- Bydliště: Doma a nebo na koleji
Potvrzuji, měl jsem zadání co tu visí z 31.5. Moc chci poděkovat všem, co sem ty zadání dávali, protože díky nim mi to snad už vyjde
Jinak ta věta co se měla dekazovat, ta podobná pumping lemmatu, asi platí, teda v písemce jsem nad tím radši ještě přemýšlel a došel jsem k tomu, že jelikož jsou reg jazyky uzavřeny na reverz, můžu z toho uvw udělat (uvw)^r a to by mělo být taky regulární. to mi dává w^rv^ru^r kde |w^r| <= p, pokud vezmu v pumping lemma n=p+|v| (což snad můžu když je v konečný) tak můžu dokázat na tomto jazyce pumping lemmatem, že je to reg a když je reg (uvw)^r, pak i uvw. Takhle jsem to tam dokázal, jestli dobře či ne, nevím. Jestli někdo neví o čem jsem psal, ať koukne na ZK 31.5.
Hodně štěstí při boji o prázdniny
Jinak ta věta co se měla dekazovat, ta podobná pumping lemmatu, asi platí, teda v písemce jsem nad tím radši ještě přemýšlel a došel jsem k tomu, že jelikož jsou reg jazyky uzavřeny na reverz, můžu z toho uvw udělat (uvw)^r a to by mělo být taky regulární. to mi dává w^rv^ru^r kde |w^r| <= p, pokud vezmu v pumping lemma n=p+|v| (což snad můžu když je v konečný) tak můžu dokázat na tomto jazyce pumping lemmatem, že je to reg a když je reg (uvw)^r, pak i uvw. Takhle jsem to tam dokázal, jestli dobře či ne, nevím. Jestli někdo neví o čem jsem psal, ať koukne na ZK 31.5.
Hodně štěstí při boji o prázdniny
- Dawe
- Supermatfyz(ák|ačka)
- Příspěvky: 360
- Registrován: 12. 10. 2004 12:32
- Typ studia: Informatika Mgr.
- Bydliště: Doma a nebo na koleji
To co jsi napsal, si myslím, že není pravda, protože tím by jsi zpochybnil i pumping lemma, kde |z|= n a |uv| = n jsou korektní podmínky pro p.l., pak tam ale patří i slovo u, kde |u| < n, čímž by jsi vyvolal spor v pumping lemma i když takový slovo je regulární.Almer píše:povrzuji...dostal jsem variantu A..
JInak, docela dlouze jsem resil , co s prikladem 10 (ten skoro pumping lemma).
Mno, vzhledem k tomu , ze |z| >= p a |w|<= p tedy vime, ze |z| >= |w|. Protoze z = u v w a v neni lambda, tudiz vime, ze |z| > |w| nebot |v|>=1. Vezmeme tedy slovo delky rovny p. Tedy takove slovo ma |v| aspom 1 a |w| maximalne p-1. vezmu li tedy maximalni slovo, tedy |u| = 0 a pumpuju dolu. Tedy mam slovo pouze z= v^0 w prvkem L, coz je ale spor s tim, ze |z|>=p.
TAKTO jsem se to snazil umlatit. CO je na tom spatne?
Nicméně z toho nevyplývá, jestli to tvrzení pravdivý je či nikoliv
-
- Matfyz(ák|ačka) level III
- Příspěvky: 103
- Registrován: 4. 6. 2005 15:49
- Typ studia: Informatika Bc.
- Bydliště: Vyšehrad
a co treba?
a co treba 1.0^n nezda se vam ze v te podmince chybi to ze ta pumpovaci cast je v tech n???
Blbost
No, to ze to nekdo dokaze pupming lemmatem je sice pekny, ale myslim si, ze chybny. PUMPING LEMMA JE NUTNA PODMINKA (NIKOLIV POSTACUJICI). Takze tim to zpusobem to dokazovat rozhodne nelze. Pumping lemma muzeme pouzivat pouze pro vylouceni toho, ze je to reg. jazyk. Na dokazani/ vylouceni lze pouzit len nerodovu vetu, coz je jak nutna tak i postacujici podminka.
Re: Blbost
V threade 31.5. 2006 je znenie zadania, nakolko je totozne s tym, co bolo na pisomke, tak to neviem:PetSvec píše:No, to ze to nekdo dokaze pupming lemmatem je sice pekny, ale myslim si, ze chybny. PUMPING LEMMA JE NUTNA PODMINKA (NIKOLIV POSTACUJICI). Takze tim to zpusobem to dokazovat rozhodne nelze. Pumping lemma muzeme pouzivat pouze pro vylouceni toho, ze je to reg. jazyk. Na dokazani/ vylouceni lze pouzit len nerodovu vetu, coz je jak nutna tak i postacujici podminka.
Takze sa to da asi dokazovat pomocou pumping lemmy, pretoze vieme, ze L je regularny, takze je splneny prvy predpoklad p.l., nie?L regularny => existuje p take, ze pre kazde |z|>=p existuju u, v a w take, ze |w| <= p, v != lambda a pre kazde i plati uv^iw patri do L.
dokaz tejto veci je takmer uplne totozny s dokazom pumping lemma (viz slajdy) s jednym malickym rozdielom:
- neuvazujeme prve a druhe navstivenie onoho inkriminovaneho stavu ale predposledne a posledne a tym je vyuzita podmienka |w| <= p lebo pocas spracovania slova w sa uz toten stav nepouzije
(uvedomil som si to az dnes na pisomke)
... snad to este niekomu pomoze
- neuvazujeme prve a druhe navstivenie onoho inkriminovaneho stavu ale predposledne a posledne a tym je vyuzita podmienka |w| <= p lebo pocas spracovania slova w sa uz toten stav nepouzije
(uvedomil som si to az dnes na pisomke)
... snad to este niekomu pomoze