Zapoctova pisemka

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
childintime
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 9. 4. 2010 15:17
Typ studia: Informatika Bc.

Zapoctova pisemka

Příspěvek od childintime »

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
Obrázek
childintime
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 9. 4. 2010 15:17
Typ studia: Informatika Bc.

Re: Zapoctova pisemka

Příspěvek od childintime »

nikdo nic? nejakou motivaci treba? tri kila tomu kdo mi to posle prvni vyreseny? fakt nevim..
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zapoctova pisemka

Příspěvek od Him »

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 ;)
MIKI
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

Příspěvek od MIKI »

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
[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
Pekny den!
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ť.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“