childintime píše: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 uviw patri L
Zoberies slovo splnujuce podmienky uvw in L & |uvw|>=n
[a3^n]
To rozdelis na 2 casti splnujuce podmienky |uv|<=n & |v|>0
[a
n|a
3^n-a
n]
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.
[a3^(n+1)]
porovnas a zistis
[an^2|a3^n-an] != [a3^(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
[an^2|a3^n-an] 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
ncb
n+1
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}
Kód: Vybrat vše
L1:
->O--a-->O->
L2:
->O<==ab==>O->
L3 = L1 prienik L2
->O--a-->O->
b\>O</ab
Pekny den!
[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!