cwbe coordinatez:
101
63540
2076399
3671716
5627765

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::1
total children::1
show[ 2 | 3] flat
Ahojte,

obratil sa na mna kamos ohladne konstrukcie Turingovho stroja, ktory akceptuje jazyk w w^R w, pricom w^R je inverzia slova w. Prikladom akceptovaneho retazca je napriklad "ahojjohaahoj", alebo "abccbaabc"...Kedze ja som sa nedostal dalej nez po zasobnikove automaty viem zostrojit maximalne w w^R ... neviete niekto poradit?

tu je zadanie formalnejsie:

vytvorit diagram pro Turinguv stroj prijimajici {ww^Rw | w nalezi do {0,1}*}

Diky.

you can live without the system but the system can not live without you




000001010006354002076399036717160562776505627850
ziman
 ziman      02.11.2010 - 00:22:38 , level: 1, UP   NEW
Ono to asi nie je neproceduralne, ale aspon teoreticke :)

Nepises, ci ma byt turingac deterministicky alebo nedeterministicky, tak ja si dovolim zvolit nedeterministicky (ma rovnaku silu a nedeterminizmus pouzivam na to, aby som nemusel explicitne vypisovat vypocet miest, kde prechadzat zo stavu do stavu). Rovnako nepises, kolko ma pasok, tak ja si zvolim dve pasky — jednu vstupnu a jednu pracovnu.

Ak mame abecedu vstupnej pasky Σ (tj. w ∈ Σ∗), tak potom si zvolime pracovno-paskovu abecedu tiez Σ. Turingacu dame tri stavy: {citam_w, citam_wR, citam_w2}.
* Turingac zacina v stave citam_w a cita zo vstupu pismena w1, w2, ..., w|w|, pricom po precitani wi zo vstupu zapise na pracovnu pasku wi a posunie pracovnu hlavu o miesto doprava. Vo vhodny okamih (nedeterministickost) sa prepne do stavu citam_wR.
* Teraz mame na pracovnej paske skopirovane slovo w. V tomto stave cita dalej pismena zo vstupnej pasky, ale na pracovnej paske sa vracia dolava a kontroluje, ci na vstupnej paske nasleduju pismena z w v opacnom poradi.
* Nakoniec sa prepne do stavu citam_w2 a kontroluje na vstupnej paske pismena w-cka v normalnom poradi.
* Po tom vsetkom skontroluje, ze sme na konci pracovnej aj vstupnej pasky.

Ak zisti nejaku nekonzistenciu, tak sa zacykli v neprijimajucom stave. Teraz ocividne existuje turingac, ktory prijme spravne formovane slovo a neexistuje turingac s tymto programom, ktory prijme nespravne formovane slovo.