Fórum studentů MFF UK

L1:
->O--a-->O->
L2:
->O<==ab==>O->

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

[quote="childintime"]nikdo nic? nejakou motivaci treba? tri kila tomu kdo mi to posle prvni vyreseny? fakt nevim..[/quote]
No po automatoch uz mam docela davno ale malo by to byt docela lahke. z pumping lematu plynie:
[b]
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[/b]

Zoberies slovo splnujuce podmienky uvw in L & |uvw|>=n
[b][a[sup]3^n[/sup]] [/b]

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
[b][uv|w] [/b]
respektive
[b][v|w][/b] (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.
[b][a[sup]3^(n+1)[/sup]][/b]
porovnas a zistis
[b][a[sup]n^2[/sup]|a[sup]3^n[/sup]-a[sup]n[/sup]] != [a[sup]3^(n+1)[/sup]][/b]

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 [b][a[sup]n^2[/sup]|a[sup]3^n[/sup]-a[sup]n[/sup]] nepatri jazyku[/b]
- 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:
-[b]v[/b] cele v aaaaaaaaaaaa-ckach
-[b]v[/b] na rozhrani aaaaaaaaa-ciek a c-cka
-[b]v[/b] cele v c-cku
-[b]v[/b] na rozhrani c-cka a bbbbbbbbbbbbbbbbbb-ciek
-[b]v[/b] 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}

[code]
L1:
->O--a-->O->
L2:
->O<==ab==>O->

L3 = L1 prienik L2
->O--a-->O->
b\>O</ab
[/code]

Pekny den!

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

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

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
[img]http://skola.jakubsamek.cz/aut1.jpg[/img]