Re[5]: 08.02.2008-16:04:20 :: Something smarter than us is going to emerge


node:	Re[5]: 08.02.2008-16:04:20
template:	4
parent:	Re[4]: 08.02.2008-16:04:20
owner:	ziman
viewed by:
created:	09.02.2008 - 22:03:32

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

ABSOLUT
KYBERIA

permissions
you:	r,
system:	public
net:	yes

PDA je dvojzasobnikovy automat? Preco sa to s PDA neda?

0000010100063540020763990367171603684355036856110368570303686790036871330368731203689739

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

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?