• Welcome to TUKE FÓRUM - Fórum pre študentov Technickej Univerzity v Košiciach.
 

Teoreticka informatika

Started by ApokalypS, 28.09.2009, 16:40:09

« predchdzajce - alie »

Pribina

no ved som pisal ze to je 4.6 u plocicu :) sorry asi som mal napisat znenie.
plllllp prepinan kapitan Spok

trek

jj ja viem :) ja len ze kolega myslel 4.5...tak aby neboli nedorozumenia :D

les paul

ahaa no potom dobre :))) ja mam totiz Príklad 4.6 Navrhnite ZA pre jazyk zátvorkových výrazov.

inak myslite si ze pre L = { (ab)n an | n>0} by mohlo byt taketo riesenie>>> ?

>>>

q0,a,Z,q0,aZ //do zasobnika davam len "a" symboly kym sa vklada (ab)n
q0,b,a,q0,a  // ked pride "b" nevkladam ho do zasobnika
q0,a,a,q0,aa
//je to nedeterministickz automat takze dalej predpokladam ze uz (ab)n skoncilo a ide an 
q0,a,a,q1,lambda  // idem do stavu q1
q1,a,a,q1,lambda
q1.lamda,Z,qF,Z  // zasobnik je prazdny takze finalny stav
Prosíme študentov, aby neodhadzovali špaky do pisoárov. Ťažko sa dofajčujú...

les paul

a podobne zasobnikovy automat pre L={0n (10)n | n>0} moze byt riesenie taketo>>> ?

>>>

q0,0,Z,q0,0Z //vkladam nuly do zasobnika
q0,0,0,q0,00 //vkladam nuly do zasobnika
q0,1,0,q1,0  //prva jednotka, idem do q1 stavu, neprepisujem symbol na vrchole
q1,0,0,q1,lambda //ked narazim na jednotku vyberem jeden symbol zo zasobnika
q1,1,0,q1,0  //ked ide jednotka nerobim nic idem dalej
q1,lambda,Z,qF,Z // finalny stav ked sa vyprazdni zasobnik
Prosíme študentov, aby neodhadzovali špaky do pisoárov. Ťažko sa dofajčujú...

puq

no mne to sedi...cize malo by to byt dobre

Quote from: les paul on  30.11.2009, 02:06:17

inak myslite si ze pre L = { (ab)n an | n>0} by mohlo byt taketo riesenie>>> ?

>>>

q0,a,Z,q0,aZ //do zasobnika davam len "a" symboly kym sa vklada (ab)n
q0,b,a,q0,a  // ked pride "b" nevkladam ho do zasobnika
q0,a,a,q0,aa
//je to nedeterministickz automat takze dalej predpokladam ze uz (ab)n skoncilo a ide an 
q0,a,a,q1,lambda  // idem do stavu q1
q1,a,a,q1,lambda
q1.lamda,Z,qF,Z  // zasobnik je prazdny takze finalny stav

Killian

Quote from: les paul on  30.11.2009, 02:14:20
a podobne zasobnikovy automat pre L={0n (10)n | n>0} moze byt riesenie taketo>>> ?

>>>

q0,0,Z,q0,0Z //vkladam nuly do zasobnika
q0,0,0,q0,00 //vkladam nuly do zasobnika
q0,1,0,q1,0  //prva jednotka, idem do q1 stavu, neprepisujem symbol na vrchole
q1,0,0,q1,lambda //ked narazim na jednotku vyberem jeden symbol zo zasobnika
q1,1,0,q1,0  //ked ide jednotka nerobim nic idem dalej
q1,lambda,Z,qF,Z // finalny stav ked sa vyprazdni zasobnik

Toto neviem ci pojde. Ak by si mal slovo 0000110000  tak ho tiez zoberie (pricom by nemalo)? Pretoze ty tam neberies do uvahy tu postupnost, ked v q1 tebe ide 1 tak nerobis nic... Alebo nie? Vie to niekto potvrdit/opravit?

buhehe

#106
myslim ze treba upravit instrukcie  3,4 a 5

q0,1,0,q1,lambda  //ked narazi na 1 vymaze 0 z vrcholu zasobnika
q1,0,0,q1,0 //ked narazi na 0 co nasleduje po tej 1, nerob nic
q1,1,0,q1,0  //dalsia 1, vymaz 0 z vrcholu zasobnika

edit: jak tak pozeram aj toto zozerie slovo 0000110000

les paul

1. dik puq za info ..snad to bdue fajn

2. killian mas pravdu ze nemam osetrene aby sa mi striedali 1 a 0

mozno taka uprava pridanim jedneho stavu este q2
q0,0,Z,q0,0Z //vkladam nuly do zasobnika
q0,0,0,q0,00 //vkladam nuly do zasobnika
q0,1,0,q1,0  //prva jednotka, idem do q1 stavu, neprepisujem symbol na vrchole
q1,0,0,q2,lambda //ked narazim na jednotku vyberem jeden symbol zo zasobnika a idem do q2 kde ocakavam ze dalsi symbol bude jednotka alebo skoncim
q2,1,0,q1,0  //ked ide jednotka nerobim nic idem dalej a zmenim stav do q1 kde cakam na nulu
q2,lambda,Z,qF,Z // finalny stav ked sa vyprazdni zasobnik
Prosíme študentov, aby neodhadzovali špaky do pisoárov. Ťažko sa dofajčujú...

Killian

Tak potom treba aj ten prvy priklad pozriet, L={ (ab)^n a^n | n>0}
Tvoje riesenie tam tusim tiez nezohladnuje striedanie sa "ab" na zaciatku, zobralo by asi aj abbbaaaa...

les paul

#109
este skuste kuk ci by toto fungovalo pre jazyk L={x patri {a,b,c}* | Na(x) = Nb(x)}

strategia je ze zapisujem len symbol "a" do zasobnika a ked pride na vstup symbol "b" tak sa vyberie "a", cim by sa malo na konci retazca narazit na dno zasobnika
q0,a,Z,q0,aZ //ked je "a" ako prvy symbol vlozim ho do zasobnika
q0,b,Z,q0,Z //ked je "b" ako prvy symbol nerobim nic s nim
q0,c,Z,q0,Z //ked je "b" ako prvy symbol nerobim nic
q0,a,a,q0,aa // symbol a vlozim
q0,b,a,q0,lambda //ked ide symbol "b" tak vyberem "a" zo zasobnika
q0,c,a,q0,a //ked ide c nerobim nic, moze byt lubovolne znakov
q0,lambda,Z,qF,Z

ked sa vlozi spravny retazec tak by to malo fungovat ak nespravny tak nastane chyba na konci ze to nebude sediet do finalneho stavu...otazka> treba to osetrit nejak?

Quote from: Killian on  30.11.2009, 02:47:42
Tak potom treba aj ten prvy priklad pozriet, L={ (ab)^n a^n | n>0}
Tvoje riesenie tam tusim tiez nezohladnuje striedanie sa "ab" na zaciatku, zobralo by asi aj abbbaaaa...

edit: nj ale ako sa to da osetrit?  striedanie (ab) sa zabezpeci extra stavom ale ako zabezpecit aby nezobral napriklad ababaaaaaaa? teda okrem toho ze nebude co uz brat zo zasobnika? to sa nebere ako chyba a HALT?
Prosíme študentov, aby neodhadzovali špaky do pisoárov. Ťažko sa dofajčujú...

anticasper

L = {a^(n+m) b^n a^m; n,m >0} nevete ako riesit tento priklad....mne co sa podarilo spravit instrukcie tak sa mi moze stat ze mi vstupi rovnaky pocet b cize b^(n+m) co je na kkt...

Killian

A tento priklad niekto riesil? L = { x|x patri {a,b}*, Na(x) = Nb(x)}
Cize moze to byt abaabb, alebo aaabbb... Musi byt iba rovnaky pocet.

Rozmyslal som, ze budem ukladat a,b do zasobnika. Napriklad mam v zasobniku A a pride B, takz zmazem A. Ale ak mam v zasobniku B a pride B, tak ho ulozim... Ale neviem ci to pojde...

(q0,a,Z,q0,aZ)
(q0,b,Z,q0,bZ)
(q0,a,a,q0,aa)
(q0,b,b,q0,bb)
(q0,a,b,q0,lambda)
(q0,b,a,q0,lambda)
(q0,lambda,Z,qF, Z)

les paul

Quote from: anticasper on  30.11.2009, 03:45:44
L = {a^(n+m) b^n a^m; n,m >0} nevete ako riesit tento priklad....mne co sa podarilo spravit instrukcie tak sa mi moze stat ze mi vstupi rovnaky pocet b cize b^(n+m) co je na kkt...

ja by som to robil takto>

q0,a,Z,q0,aZ //vkladam a do zasobnika
q0,a,a,q0,aa //vkladam a do zasobnika
q0,b,a,q1,lambda
q1,b,a,q1,lambda //nacitava b, maze a zo zasobnika
q1,a,a,q2,lambda   //pride na vstup "a" tak idem do q2 aby som osetril ze uz mozu ist len a, popritom mazem a zo zasobnika
q2,a,a,q2,lambda
q2.lambda,Z,qF,Z
Prosíme študentov, aby neodhadzovali špaky do pisoárov. Ťažko sa dofajčujú...

cepi

OK a co ak dojde potadeto:

q0,a,Z,q0,aZ //vkladam a do zasobnika
q0,a,a,q0,aa //vkladam a do zasobnika
q0,b,a,q1,lambda
q1,b,a,q1,lambda //nacitava b, maze a zo zasobnika

a teda sa zasobnik vyprazdni, a na konci pasky uz nebude nic, daka mudra veta vravi ze zasobnik knoci cinnost bud to vyprazdnenim alebo prechodom do finalneho stavu.

takze ked budem mat aaaabbbb tak sa vyprazdni a skoncil cinnosti nie ? a teda akceptoval slovo ktore tam nema co hladat ? ak taram tak ma opravte
som kto som vdaka palenke

Killian

Ten moj uz netreba riesit, v plocicovych je to presne tak vyriesene. Takze Ok.

johnyo13

ma niekto nejake vyriesene priklady na touringove stroje, bo ja mam asi tak 2 ci 3 a rad by som este nejake pozrel :)
☼Ѿ☼ ... ☼Ѿ☼

Killian

Ja by som sa este vratil ku Plocicovemu prikladu 4.6

Navrhnite za pre jazyk L = {x ∈ {a, b}∗,Na(x) = 2.Nb(x)}
Inac povedane pismen A bude dvakrat tolko ako B. Mozu sa akokolvek striedat.
Takze spravne slovo je aaaabb, ale aj baaaab.

Robil by som to tak, ze ak najdem b, tak ho ulozim dvakrat, aby som to vykompenzoval

q0,a,Z,q0,aZ
q0,b,Z,q0,bbZ
q0,a,a,q0,aZ
q0,b,b,q0,bbZ
q0,b,a,q0,lambda
q0,a,b,q0,lambda
q0,lambda,Z,qF,Z

Jeho riesenie nechapem:
(q0, a,Z, q1, aZ)
(q0, a, a, q1, aa)
(q0, b, a, q0, lambda)
(q0, b,Z, q0, bbZ)
(q0, b, b, q0, bbb)
(q0, a, b, q0,lambda)
(q1, a, a, q0, a)
(q1, b, a, q1,lambda)
(q1, b,Z, q1, bbZ)
(q1, b, b, q1, bbb)
(q1, a, b, q1, lambda)
(q1, a,Z, q0, a)
(q0,lambda,Z, q0, lambda)

Co je na mojom zle? Uz mam v tom chaos.

buhehe

Quote from: Killian on  30.11.2009, 04:31:54
q0,a,Z,q0,aZ
q0,b,Z,q0,bbZ
q0,a,a,q0,aZ
q0,b,b,q0,bbZ
q0,b,a,q0,lambda
q0,a,b,q0,lambda
q0,lambda,Z,qF,Z
skus slovo abaabbaaa...neprejde ti

btw par stran dozadu je riesnie od Pribinu

Killian

#118
Aha.. cumim do toho ale nechapem ako to spravil..  A to som prestudoval aj http://necyklopedie.wikia.com/wiki/Turing%C5%AFv_stroj  ;D ;D.

Nemoze niekto ku tomu slovny komentar prosim napisat? Nemal tam niekde dva B naraz ukladat do zasobnika?

Aby ste nemuseli listovat, tu je Pribinove riesenie
L = {x ∈ {a, b}∗,Na(x) = 2.Nb(x)}

(q0, a, Z, q1, Z)
(q0, b, Z, q0, bZ)
(q0, b, b, q0, bb)
(q0, a, b, q1, b)
(q0, a, a, q1, a)
(q0, b, a, q0, lambda)
(q1, a, a, q0, aa)
(q1, b, a, q1, lambda)
(q1, a, b, q0, lambda)
(q1, b, b, q1, bb)
(q1, a, Z, q0, aZ)
(q1, b, Z, q1, bZ)
(q0, lambda, Z, qF, Z)

puq

tak ked si turinga pri zasobnikovych studoval tak sa necudujem :D :D

ale ide o to:

len pre zaciatok...stav q0 znamena ze je na vstupe prve "a" a stav q1 ze je na vstupe druhe "a" kedze "a"cka maju byt 2x viac bcka...prve acko sa bude ignorovat...iba druhe acko sa bude ukladat do zasobnika...a funguje to nasledovne ak mame napriklad abaaab tak:

pride "a" to odignorujeme a zmenime stav na q1...tam ulozime bcko do zasobnika...nasledne pride dalsie a...vieme ze je to druhe "a" tak mozeme b-cko vybrat zo zasobnika a nic tam nevlozime a zmenime stav naspat na q0...opat prve acko ignorujeme a ideme do stavu q1...v tom stave vlozime do zasobnika "a" a opat zmenime stav na q0...tak nam pride "b" a kedze mame v zasobniku "a" tak ho mozeme vybrat a potom skoncime....

Pribina

Quote from: johnyo13 on  30.11.2009, 04:14:30
ma niekto nejake vyriesene priklady na touringove stroje, bo ja mam asi tak 2 ci 3 a rad by som este nejake pozrel :)

Ak chces precvicovat TS, tak to mozes skusat na tych istych zneniach co su tu na fore pri zasobnikovych automatoch. Pri niektorych, neskusal som vsetky, ide vytvorit instrukcie aj pre TS (napr. pre L = {a^(n+m) b^n a^m | n,m >0}).
plllllp prepinan kapitan Spok

Sooloni

kedy, kde a s kym su cvika v utorok z TI?

BossZ

<iframe style="width:300px;height:600px;padding:0;margin: -300px 0px 0px 0px;border:0;" marginwidth="0" marginheight="0" hspace="0" vspace="0" frameborder="0" scrolling="no" src="http://www.androidroka.sk/wp-content/themes/androidRoku/iframe.php?invite=52633e266001a22a5eb0166ee736bc68"></iframe>


kOsTi

niekto uz ma asi dost z toho ucenia :)
:trestac: