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

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?

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

Almer wrote: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?

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

Nicméně z toho nevyplývá, jestli to tvrzení pravdivý je či nikoliv :-)

Právě jsem svoje řešení toho příkladu postnul o thread vedle ;)

a co treba 1.0^n nezda se vam ze v te podmince chybi to ze ta pumpovaci cast je v tech n???

No dyť se nikde neříká, kde se bude pumpovat, stejně jako v pumping lemma. A když vezmu slovo délky p, 10^(p-1) a w=p-2 (splňuje |w|<=p) a vezmu u=1, v=0, w=0^(p-2), pak můžu pumpovat v, nahoru i dolů.

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

PetSvec wrote: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. :)

V threade 31.5. 2006 je znenie zadania, nakolko je totozne s tym, co bolo na pisomke, tak to neviem:

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.

Takze sa to da asi dokazovat pomocou pumping lemmy, pretoze vieme, ze L je regularny, takze je splneny prvy predpoklad p.l., nie?

Myslím, že to zadání je totožný, už jsem to psal jednou nahoře. :-)

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