cwbe coordinatez:
101
63540
2076399
3671716
3684355
3685611
3685703

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
Teraz sa ti podarilo dostat moju statnicami ovplyvnenu pamat do rekurzie :), pretoze povodne som mal v umysle napisat, ze by na to stacil aj abycajny automat implementujuci regularnu gramatiku S -> 1S | 0S | epsilon, ale ked nad tym tak uvazujem, tak by na riesenie tohto problemu nebol dostatocny lebo by si nedokazal pamatat pocet jednotiek, ktore uz presiel aj ked datovu strukturu Bitseq by vpohode generoval. Napadlo ma, ci to nie je schopny riesit zasobnikovy automat s dvoma zasobnikmi... Turingov stroj ako konstrukt s nekonecnou paskou to urcite dokaze, kedze podla Alana Turinga dokaze realizovat lubovolny algoritmicky riesitelny problem. Stale mi vrta hlavou ten zasobnikovy automat lebo imho by to nemal byt tak zlozity problem, ale nejako sa mi nedari vyplodit prechodovu funkciu a celkovo strukturu PDA o tejto hodine. Snad niekto z pritomnych bude uspesnejsi...

Don\'t Tase Me, Bro!




0000010100063540020763990367171603684355036856110368570303686790
ziman
 ziman      09.02.2008 - 18:02:40 , level: 1, UP   NEW
Prehadzovanie prvkov medzi dvoma zasobnikmi je ekvivalentne posuvaniu sa po paske.

000001010006354002076399036717160368435503685611036857030368679003687133
piece_of_IT
 piece_of_IT      09.02.2008 - 20:31:24 , level: 2, UP   NEW
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: 3, 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: 4, 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: 5, 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?