Teoreticka informatika

[Pribina]

no ved som pisal ze to je 4.6 u plocicu sorry asi som mal napisat znenie.

[trek]

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

[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)ⁿ aⁿ | n>0} by mohlo byt taketo riesenie>>> ?

>>>

q0,a,Z,q0,aZ //do zasobnika davam len "a" symboly kym sa vklada (ab)ⁿ
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)ⁿ skoncilo a ide aⁿ 
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

[les paul]

a podobne zasobnikovy automat pre L={0ⁿ (10)ⁿ | 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

[puq]

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

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

>>>

q0,a,Z,q0,aZ //do zasobnika davam len "a" symboly kym sa vklada (ab)ⁿ
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)ⁿ skoncilo a ide aⁿ 
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]

a podobne zasobnikovy automat pre L={0ⁿ (10)ⁿ | 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]

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

[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]

este skuste kuk ci by toto fungovalo pre jazyk L={x patri {a,b,c}* | N_a(x) = N_b(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?

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?

[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]

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

[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

[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]

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]

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

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

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]

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}).

[Sooloni]

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

[BossZ]

portal

[Casso]

portal

aky?:-DDD

[kOsTi]

niekto uz ma asi dost z toho ucenia