# ZK 2009-06-23

<{ForumPost(poster="Him", timestamp=2009-06-23 13:08:18)}>
Od kamarada jsem ziskal otazky, ktere mel na "ustni" casti:  
  
* napsat TS pro palindromy  
* urcit do jaky skupiny podle Chomskeho jazyk patri a dokazat to  
  
  
Zkousel jsem si to resit, kdybyste nasli chybu tak kricte:  
  
**1]** Jenom slovne: Prectu prvni pismeno a ulozim si ho do stavu, na danou pozici dam specialni symbol s vyznamem "sem uz nechod". Pak bych jel s tim pismenem na konec a pokud by se schodovalo ulozene pismenko s poslednim, tak bych na tom poslednim znaku zase dal symbol "sem uz nechod". Takhle bych jezdil z jedne strany na druhou. Pokud bych dostal na konci prazdnou pasku, tak bych se prepnul do koncoveho stavu. Pokud bych narazil na spatne pismenko v prubehu prejizdeni z jedne strany na druhou, tak bych se prepnul do stavu, pro ktery neni definovana prechodova fce a tim skoncil.   
  
Pozn. "sem uz nechod" ~ epsilon  
  
**2]**  
  
Myslenka:   
      1) Ukazu, ze jazyk neni regularni   
      2) udelam bezkontextovou gramatiku pro palindromy.   
  
ad 1)Pro spor predpokladejme, ze jazyk je regularni. Dle Nerodovy vety existuje prava kongruence ~ konecneho indexu m na X* takova, ze L je sjednocenim jistych trid rozkladu X*/~.  
  
Vezmu slova:  
  
B  
AB  
AAB  
...  
A^(m+1)B  
  
A a B jsou pismena abecedy  
  
Dve slova padnou do stejne tridy ekvivalence (Dirichlet), oznacme je A^i.B a A^j.B (i /= j), plati pro ne tedy:  
  
A^i.B ~ A^j.B  
  
~ je prava kongruence, tedy ma platit:  
  
A^i.B.A^(m-i)   ~  A^j.B.A^(m-i)        // pridam retezec A^(m-i) k oboum slovum  
  
nicmene A^i.B.A^(m-i) \in L ale A^j.B.A^(m-i)   
otIN L  -- spor   
  
Pozn. Pokud abeceda obsahuje pouze jedno pismeno, pak je L jiste regularni. Bezkontextovy je pro |X|>1
<{/ForumPost}>

<{ForumPost(poster="Kubees", timestamp=2009-06-23 15:17:55)}>
Ahoj,  
  
huh, chvilku mi trvalo, nez jsem ten dukaz pobral, ale uz dobry, rozumim :-)  
  
Jeste dodam ze podobnym zpusobem se totez da dokazat pres pumping lemma:  
AAAABAAAA  :arrow:  patri do jazyka  :arrow: napumpuju levou pulku  :arrow: AAAAAAAABAAA  :arrow: nepatri do jazyka  :arrow: spor  
  
Samozrejme je opet treba rict, ze toto plati pro slova delky > 2n kde n je vzdalenost pumpovane casti, ne pro tohle konkretni slovo, ale to je snad kazdemu jasne.  :)
<{/ForumPost}>