Fórum studentů MFF UK

Zadani od Surynka na zapoctove pisemky( http://ktiml.mff.cuni.cz/~surynek/teach ... 5-2008.pdf )
1)
Dána gramatika G = (VT ,VN ,S,P), kde V= {a,b}, VN = {S, A,B,C,D} a P = {S -> aSbA |lambada ; A -> aBbA| bCB |CD;B -> bbBa | aS;C -> aAaA|lambada ;D -> SC | aABb}. Je gramatika G kontextová? Je jazyk generovaný gramatikou G kontextový? Pokud ano, napište ekvivalentní kontextovou gramatiku.

-- kontextova neni lebo S->lambada a vyskytuje se na prave strane a pak C->lambada!.


2)Navrhněte zásobníkový automat přijímající jazyk L nad abecedou X = {a,b,c}, kde L={ucv|u,v \in {a,b}* &u!=v}.

3)Navrhněte gramatiku, která generuje jazyk L nad abecedou X = {a,b}, kde L={a^pb^q|p,q jsou prvočísla & p ≠ q}. Lze vůbec tento úkol splnit?

--gramatika generuje slova s jistou pravidelnosti, kdezto prvocisla jsou rozdelena nerovnomerne (nebo zatim neobevil nejakou obecnou pravidelnost) -> takova gramtika neexistuje?

Sedi? Ma nekdo jine reseni?

Myslim, ze se s nim o tom po pisemce nekdo bavil a rikal, ze ten ukol splnit jde, protoze to, ze je cislo prvocislem, zjistim Pascalem ~ Turinguv stroj (tuhle uvahu uz jsem nekolikrat slysel, jen ji moc neverim ) a Turinguv stroj -> jazyky typu 0.

Neviete ako je to s tym, ked niekto nesplna aktivitu a ma obe testy + dochadzku? Skusal sa niekto dohodnut?

Ja nechodil na cviceni vubec a Surynek pozadoval vypracovani ukolu ke cvicenim ze stranky Romana Bartaka jako nahradu za dochazku a aktivitu. Mel jsem to ale domluvene od zacatku semestru.

Caute,
neviete, ako na tento priklad z dnesnej pisomky? Mali ste to niekto?

3) Navrhnite gramatiku, ktora generuje jazyk L nad abecedou X = {a}, kde L = {a^(x^3) | x = 0, 1, 2 ... }.