cwbe coordinatez:
101
63540
2076399
3671716
3684355
3685611
3685703
3686790
3687133

ABSOLUT
KYBERIA
permissions
you: r,
system: public
net: yes

neurons

stats|by_visit|by_K
source
tiamat
K|my_K|given_K
last
commanders
polls

total descendants::
total children::1
show[ 2 | 3] flat
No dnes som to riesil s kamosom a dospeli sme k zaveru, ze PDA by to tak ci tak nebol defaultne schopny realizovat, takze riesenie je spominane TM.

www.hackujeme.sk - The Real Hardcore in ICT Security




00000101000635400207639903671716036843550368561103685703036867900368713303687312
ziman
 ziman      09.02.2008 - 22:03:32 , level: 1, UP   NEW
PDA je dvojzasobnikovy automat? Preco sa to s PDA neda?

0000010100063540020763990367171603684355036856110368570303686790036871330368731203689739
piece_of_IT
 piece_of_IT      10.02.2008 - 23:01:52 (modif: 10.02.2008 - 23:06:57), level: 2, UP   NEW !!CONTENT CHANGED!!
ano PDA je zas. automat [Pushdown automaton], ale vseobecne (nie nevyhnutne s 2ma zasobnikmi). Hmm no ono v principe by to mozne teoreticky bolo, ale podla definicie neviem spravit funciu, ktora by tie acka, co ma nasackovane na zasobniku cez prechodovy funciu pustala a zaroven zvysovala citac, ktory by nakoniec vyplula a akceptovala koncovy stav prazdnym zasobnikom. Takto by to teoreticky fungovalo, otazka je, ci je PDA schopne pricitavat (1+) a nakoniec vyhodit numericky vysledok. Tam s mojimi sucansnymi znalostami nesiaham. Ak uvedies protipriklad a potvrdis, ze je to mozne aj prakticky, budem len rad.

Ono vpodstate PDA sluzi na generovanie bezkontextovych jazykov, takze si schopny na nom vpohode vygenerovat napriklad slova jazyka a^n.b^n, ale nieco ako numericke vypocty zrejme nedokaze realizovat.

www.hackujeme.sk - The Real Hardcore in ICT Security

000001010006354002076399036717160368435503685611036857030368679003687133036873120368973903689901
ziman
 ziman      11.02.2008 - 00:24:13 , level: 3, UP   NEW
pozor! automat s dvoma zasobnikmi uz nie je PDA.

Urcite vies, ze a^i.b^i.c^i nie je bezkontextovy jazyk, ale da sa zriesit automatom z dvoma zasobnikmi (trivialne) -- zjavny protipriklad.

Oznacme si zasobniky A, B. Potom istrukcie TS sa prekladaju na instrukcie dvojzasobnikoveho automatu nasledovne:
pohyb vlavo: push A (pop B)
pohyb vpravo: push B (pop A)
bunka pod hlavou: peek A
pricom pop z prazdneho zasobnika vrati epsilon
to sa tyka realizacie pasky dvoma zasobnikmi. Zvysok automatu je rovnaky.

mylim sa niekde?