Zapoctova pisemka

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

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

Podivej se do studnice, je tam naskenova knizka o Automatech s resenymi priklady - nejaka podoba toho prvniho tam bude.

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ⁱw patri L**

Zoberies slovo splnujuce podmienky uvw in L & |uvw|>=n
**[a^{3^n}] **

To rozdelis na 2 casti splnujuce podmienky |uv|<=n & |v|>0
[aⁿ|a^{3^n}-aⁿ]

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^{3^(n+1)}]
   porovnas a zistis
   [a^{n^2}|a^{3^n}-aⁿ] != [a^{3^(n+1)}]

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^{n^2}|a^{3^n}-aⁿ] 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ⁿcbⁿ⁺¹
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!