# Zapoctove priklady Pavel Surynek chutovky

<{ForumPost(poster="lickra", timestamp=2008-06-09 23:02:05)}>
Zadani od Surynka na zapoctove pisemky( [http://ktiml.mff.cuni.cz/~surynek/teach ... 5-2008.pdf](http://ktiml.mff.cuni.cz/~surynek/teaching/2007_2008-LS/automaty_a_gramatiky/files/automaty_pisemka-06-05-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?
<{/ForumPost}>

<{ForumPost(poster="lj8", timestamp=2008-06-10 20:53:30)}>
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.
<{/ForumPost}>

<{ForumPost(poster="ansh2", timestamp=2009-06-03 11:30:34)}>
Neviete ako je to s tym, ked niekto nesplna aktivitu a ma obe testy + dochadzku? Skusal sa niekto dohodnut?
<{/ForumPost}>

<{ForumPost(poster="Kubees", timestamp=2009-06-04 00:30:56)}>
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.
<{/ForumPost}>

<{ForumPost(poster="thoth", timestamp=2009-06-04 14:45:33)}>
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 ... }.
<{/ForumPost}>