Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

PDA zadatak
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Matematička teorija računarstva
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
Mojo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 28. 02. 2006. (12:37:23)
Postovi: (3F)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 18:15 pon, 25. 8. 2008    Naslov: PDA zadatak Citirajte i odgovorite

Ajde ako bi itko mogao rjesiti ovaj zadatak ili ga prepisat sa svojih vjezbi jer je rjesen na njima (na mojim vjezbama je krivo rjesen). Zadatak glasi: Konstruirati PDA automat koji prepoznaje jezik

L = {w € (a+b+c)^* | |w|_a = 2|w|_b }
Ajde ako bi itko mogao rjesiti ovaj zadatak ili ga prepisat sa svojih vjezbi jer je rjesen na njima (na mojim vjezbama je krivo rjesen). Zadatak glasi: Konstruirati PDA automat koji prepoznaje jezik

L = {w € (a+b+c)^* | |w|_a = 2|w|_b }


[Vrh]
Korisnički profil Pošaljite privatnu poruku
greeneyes
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 09. 2004. (11:44:20)
Postovi: (CD)16
Spol: žensko
Sarma = la pohva - posuda
36 = 47 - 11
Lokacija: The water's edge Is where she waits

PostPostano: 22:17 pon, 25. 8. 2008    Naslov: Citirajte i odgovorite

ideja: u pocetnom stanju [latex]q_0[/latex] stog je prazan, mozemo citati a, b ili c - ako procitamo c, samo citamo sljedeci znak; ako procitamo a, zapisemo a na stog i prelazimo u stanje [latex]q_1[/latex]; ako procitamo b stavljamo 2 b na stog i prelazimo u stanje [latex]q_3[/latex]. u stanju [latex]q_1[/latex] a-ove stavljamo na stog, c-ovi nista ne mijenjaju, a b-ovi skidaju dva a sa stoga (ako ima manje a-ova na stogu, zapisuje se toliko b-ova koliko ih fali i ode u stanje [latex]q_3[/latex]). u stanju [latex]q_3[/latex] ako citamo b, dva b idu na stog, ako citamo c, nista se ne mijenja, a ako citamo a skidamo b sa stoga - ako se b ne moze skinuti, pisemo a na stog i prelazimo u stanje [latex]q_1[/latex]. rijec se prihvaca praznim stogom ako se [latex]\varepsilon[/latex] procita u stanju [latex]q_1[/latex] ili [latex]q_3[/latex]

oblik zapisa je <stanje, znak na ulazu, znak na vrhu stoga, stanje u koje se ide, sto ide na stog>, pisala sam jos i komentare just in case..

/*citanje prvog znaka, za procitani b trebamo upisati 2 b na stog pa nam treba dodatno stanje, ovdje [latex]q_2[/latex]*/

[latex]
<q_0, a, \varepsilon, q_1, a> \\
<q_0, b, \varepsilon, q_2, b>, \; <q_2, \varepsilon, b, q_3, b> \\
<q_0, c, \varepsilon, q_0, \varepsilon> \\
[/latex]

gdje je smisao [latex]<q_2, \varepsilon, b, q_3, b>[/latex] - u stanju [latex]q_2[/latex] smo, ne citamo nista, na stogu je b; prelazimo u stanje [latex]q_3[/latex] i pisemo b na stog

/*stanje [latex]q_1[/latex] - stavljamo a-ove na stog, s b-ovima skidamo po dva a, dakle, stog moze u nekom trenu biti prazan pa zato za svaki procitani znak treba gledati obje mogucnosti - da li je stog prazan ili je na njemu a*/

[latex]
<q_1, a, a, q_1, a> \\
<q_1, a, \varepsilon, q_1, a> \\
<q_1, c, a, q_1, \text{ne diramo stog}> \\
<q_1, c, \varepsilon, q_1, \varepsilon> \\
(*) <q_1, b, a, q_4, \varepsilon>, \; <q_4, \varepsilon, a, q_1, \varepsilon>, \; <q_4, \varepsilon, \varepsilon, q_3, b> \\
<q_1, b, \varepsilon, q_2, b>
[/latex]

smisao [latex](*)[/latex] je - skinemo jedan a sa stoga ako mozemo (ako ne - vidi sljedeci red) i odemo u stanje [latex]q_4[/latex] gdje ili skinemo jos jedan a, ili ako to ne mozemo, zapisemo b na stog i promijenimo stanje u [latex]q_3[/latex] jer su sad na stogu b-ovi

/*stanje [latex]q_3[/latex] - citanje a ubije b na stogu ako moze, citanje b stavlja 2 b na stog - opet se moze dogoditi da je stog u nekom trenu prazan pa i to treba uzeti u obzir*/

[latex]
<q_3, b, b, q_2, b> \\
<q_3, b, \varepsilon, q_2, b> \\
<q_3, c, b, q_3, \text{ne diramo stog}> \\
<q_3, c, \varepsilon, q_3, \varepsilon> \\
<q_3, a, b, q_3, \varepsilon> \\
<q_3, a, \varepsilon, q_1, a>
[/latex]

/*prihvacanje rijeci*/

[latex]
<q_1, \varepsilon, \varepsilon, q_1, \varepsilon> \\
<q_3, \varepsilon, \varepsilon, q_3, \varepsilon> \\
[/latex]

---

oznake su malo zeznute - za brisanje sa stoga koristimo [latex]<q, x, y, r, \varepsilon> [/latex], a treba nam nesto slicno za situaciju kad se stog ne dira (citanje c-ova) - ako cu opet kao zadnju komponentu pisati [latex]\varepsilon[/latex] u smislu da nista nejde na stog, ispada da zapravo nesto brisem - zato sam radije pisala rijecima (za slucaj da je stog prazan je svejedno)

nadam se da je razumljivo i da nema neke greske ;)
ideja: u pocetnom stanju stog je prazan, mozemo citati a, b ili c - ako procitamo c, samo citamo sljedeci znak; ako procitamo a, zapisemo a na stog i prelazimo u stanje ; ako procitamo b stavljamo 2 b na stog i prelazimo u stanje . u stanju a-ove stavljamo na stog, c-ovi nista ne mijenjaju, a b-ovi skidaju dva a sa stoga (ako ima manje a-ova na stogu, zapisuje se toliko b-ova koliko ih fali i ode u stanje ). u stanju ako citamo b, dva b idu na stog, ako citamo c, nista se ne mijenja, a ako citamo a skidamo b sa stoga - ako se b ne moze skinuti, pisemo a na stog i prelazimo u stanje . rijec se prihvaca praznim stogom ako se procita u stanju ili

oblik zapisa je <stanje, znak na ulazu, znak na vrhu stoga, stanje u koje se ide, sto ide na stog>, pisala sam jos i komentare just in case..

/*citanje prvog znaka, za procitani b trebamo upisati 2 b na stog pa nam treba dodatno stanje, ovdje */



gdje je smisao - u stanju smo, ne citamo nista, na stogu je b; prelazimo u stanje i pisemo b na stog

/*stanje - stavljamo a-ove na stog, s b-ovima skidamo po dva a, dakle, stog moze u nekom trenu biti prazan pa zato za svaki procitani znak treba gledati obje mogucnosti - da li je stog prazan ili je na njemu a*/



smisao je - skinemo jedan a sa stoga ako mozemo (ako ne - vidi sljedeci red) i odemo u stanje gdje ili skinemo jos jedan a, ili ako to ne mozemo, zapisemo b na stog i promijenimo stanje u jer su sad na stogu b-ovi

/*stanje - citanje a ubije b na stogu ako moze, citanje b stavlja 2 b na stog - opet se moze dogoditi da je stog u nekom trenu prazan pa i to treba uzeti u obzir*/



/*prihvacanje rijeci*/





oznake su malo zeznute - za brisanje sa stoga koristimo , a treba nam nesto slicno za situaciju kad se stog ne dira (citanje c-ova) - ako cu opet kao zadnju komponentu pisati u smislu da nista nejde na stog, ispada da zapravo nesto brisem - zato sam radije pisala rijecima (za slucaj da je stog prazan je svejedno)

nadam se da je razumljivo i da nema neke greske Wink



_________________
Am I so different from you
Now does it scare you that I'm able to discern
What to love and what to burn..
Don't judge what you don't understand..

// Disturbed: Fear
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Mojo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 28. 02. 2006. (12:37:23)
Postovi: (3F)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 15:24 uto, 26. 8. 2008    Naslov: Citirajte i odgovorite

Vjecno zahvalan zelenooka.

Mojo Jojo


Samo da provjerim, u slucaju kad je 3|w|_a = 2|w|_b, onda je sve isto, samo kad procitam a, u stanjima q_0 i q_1, stavljam ih 3 na stog, i u q_3 jedan a brise 3 b sa stoga ili upisuje a-ova koliko fali, ako fali.
Vjecno zahvalan zelenooka.

Mojo Jojo


Samo da provjerim, u slucaju kad je 3|w|_a = 2|w|_b, onda je sve isto, samo kad procitam a, u stanjima q_0 i q_1, stavljam ih 3 na stog, i u q_3 jedan a brise 3 b sa stoga ili upisuje a-ova koliko fali, ako fali.


[Vrh]
Korisnički profil Pošaljite privatnu poruku
greeneyes
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 09. 2004. (11:44:20)
Postovi: (CD)16
Spol: žensko
Sarma = la pohva - posuda
36 = 47 - 11
Lokacija: The water's edge Is where she waits

PostPostano: 20:49 uto, 26. 8. 2008    Naslov: Citirajte i odgovorite

da (uz oznake [latex]q_0[/latex] pocetno stanje, [latex]q_1[/latex] stanje u kojem a-ove gomilamo na stog i [latex]q_3[/latex] stanje u kojem b-ove gomilamo na stog) - ako u [latex]q_0, q_1[/latex] citamo a idu 3a na stog, ako u [latex]q_1[/latex] citamo b, skidamo 2a sa stoga i ostajemo u istom stanju ili skinemo koliko moze a-ova, stavimo koliko je falilo b-ova i promijenimo stanje; ako u [latex]q_0, q_3[/latex] citamo b idu 2b na stog, a ako u [latex]q_3[/latex] citamo a, skidamo 3b sa stoga i ostajemo u istom stanju ili skinemo koliko ide, dodamo a-ova koliko je falilo i promijenimo stanje

no frx, happy to help ;)
da (uz oznake pocetno stanje, stanje u kojem a-ove gomilamo na stog i stanje u kojem b-ove gomilamo na stog) - ako u citamo a idu 3a na stog, ako u citamo b, skidamo 2a sa stoga i ostajemo u istom stanju ili skinemo koliko moze a-ova, stavimo koliko je falilo b-ova i promijenimo stanje; ako u citamo b idu 2b na stog, a ako u citamo a, skidamo 3b sa stoga i ostajemo u istom stanju ili skinemo koliko ide, dodamo a-ova koliko je falilo i promijenimo stanje

no frx, happy to help Wink



_________________
Am I so different from you
Now does it scare you that I'm able to discern
What to love and what to burn..
Don't judge what you don't understand..

// Disturbed: Fear
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Matematička teorija računarstva Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan