# Zapoctova pisemka

<{ForumPost(poster="childintime", timestamp=2010-04-09 15:26:02)}>
pred tydnem jsem psal zapoctovou pisemku, nedopadla mi uplne nejlepe a byl bych rad kdyby mohl nekdo napsat jak se meli jednotlive priklady resit. Jedine cim jsem si jisty ze mam spravne je priklad 3. :)   
diky moc  
[http://skola.jakubsamek.cz/aut1.jpg](http://skola.jakubsamek.cz/aut1.jpg)
<{/ForumPost}>

<{ForumPost(poster="childintime", timestamp=2010-04-12 23:28:38)}>
nikdo nic? nejakou motivaci treba? tri kila tomu kdo mi to posle prvni vyreseny? fakt nevim..
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2010-04-13 01:14:40)}>
Podivej se do studnice, je tam naskenova knizka o Automatech s resenymi priklady - nejaka podoba toho prvniho tam bude.
<{/ForumPost}>

<{ForumPost(poster="MIKI", timestamp=2010-04-30 11:10:09)}>

 > childintime wrote:nikdo nic? nejakou motivaci treba? tri kila tomu kdo mi to posle prvni vyreseny? fakt nevim..

No po automatoch uz mam docela davno ale malo by to byt docela lahke. z pumping lematu plynie:  
**  
L je reg =>   
Ex n >0  kde  
uvw in L & |uvw|>=n & |uv|<=n & |v|>0 ,  
take ze uv<sup>i</sup>w patri L**  
  
Zoberies slovo splnujuce podmienky uvw in L & |uvw|>=n  
**\[a<sup>3^n</sup>] **  
  
To rozdelis na 2 casti  splnujuce podmienky  |uv|<=n & |v|>0   
\[a<sup>n</sup>|a<sup>3^n</sup>-a<sup>n</sup>]  
  
Coz odpoveda    
**\[uv|w] **  
respektive   
**\[v|w]**  (pri u=lanbda -aby sa to mohlo co najviac nafuknut)  
  
1) moznost (nie uplne formalny dokaz - spravne by sa mala dokazovat prislusnost slova k jazyku)  
No a teraz uz len skusis zapumpovat hore a porovnas s dalsim slovom patricim do jazyka  tj.   
**\[a<sup>3^(n+1)</sup>]**  
porovnas a zistis  
**\[a<sup>n^2</sup>|a<sup>3^n</sup>-a<sup>n</sup>] != \[a<sup>3^(n+1)</sup>]**  
  
2) moznost (formalne spravna - dokazat aj dalsie pripady)  
dokazes rozborom pripadov tj. pri lubovolnom zvoleni slova uv a zapunpovani to nikdy nebude patrit do jazyka. Uz len rozoberies pripady ako by mohlo rozdelenie skoncit a zapumpujes. Je jasne, ze ked si zvolis uv akokolvek a zapumpujes, stale ti pribuda/ubuda malo znakov na to aby to mohlo patrit do jazyka.   
- Prvy pripad (u=lambda) mas hotovy pretoze **\[a<sup>n^2</sup>|a<sup>3^n</sup>-a<sup>n</sup>] nepatri jazyku**  
- dalsie ukazes, ze ak to zvolis akokolvek tj 0<|v|<n tak to nepatri jazyku (tiez trivialne)  
Ak sa ti nepodari zapumpovat tak ze slovo vzniknute po zapumpovani patri L (coz by sa ti nemalo) tak je to spor a L nemoze byt regularny, pretoze keby bol musel by ist pumpovat.  
  
  
Ku dvojke to iste  
vylucuje to pripad a<sup>n</sup>cb<sup>n+1</sup>  
tj pripady ktore dokazes:  
-**v** cele v aaaaaaaaaaaa-ckach  
-**v** na rozhrani aaaaaaaaa-ciek a c-cka  
-**v** cele v c-cku  
-**v** na rozhrani c-cka a bbbbbbbbbbbbbbbbbb-ciek  
-**v** cele v bbbbbbbbbbbbb-ckach  
  
Stvorka zostrojis k jazykom automaty a uz len prekladas hrany tj zacnes od vstupu a pridavas len tie prechodove fcie ktore su v oboch automatoch + osetris v podobe mrtveho stavu. Ak medzi vstupom a vystupom neexistuje cesta prienik je {}  
trebars  
X1 = {a}  
X2 = {a,b}  

    L1:
    ->O--a-->O->
    L2:
    ->O<==ab==>O->
    
    L3 = L1 prienik L2
    ->O--a-->O->
      b\>O</ab
    

Pekny den!
<{/ForumPost}>