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
Zapoctova pisemka
-
- Matfyz(ák|ačka) level I
- Příspěvky: 2
- Registrován: 9. 4. 2010 15:17
- Typ studia: Informatika Bc.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 2
- Registrován: 9. 4. 2010 15:17
- Typ studia: Informatika Bc.
Re: Zapoctova pisemka
nikdo nic? nejakou motivaci treba? tri kila tomu kdo mi to posle prvni vyreseny? fakt nevim..
Re: Zapoctova pisemka
Podivej se do studnice, je tam naskenova knizka o Automatech s resenymi priklady - nejaka podoba toho prvniho tam bude.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 10. 12. 2004 22:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: Zapoctova pisemka
No po automatoch uz mam docela davno ale malo by to byt docela lahke. z pumping lematu plynie:childintime píše:nikdo nic? nejakou motivaci treba? tri kila tomu kdo mi to posle prvni vyreseny? fakt nevim..
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
[an|a3^n-an]
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 ancbn+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
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.