Matematické Fórum

Je to dosť dávno, odkedy som naposledy robil niečo s TS, takže možno prehliadnem nejaký problém, ale možno by to šlo takto:

Zakaždým zmazať jedno x z prvej pásky a na druhú pásku si zapisovať počet x-ov, ktoré som zmazal v trojkovej sústave, t.j. 0,1,2,10,11,12,20,...

Keď prečítam celý vstup, tak sa pozriem, či mám na druhej páske číslo, ktoré má na najvyššom mieste jednotku a potom samé nuly.

(Používam dvojpáskový TS, ale aj ty si písal o druhej páske.)

meron napsal(a):

jen mi teda není jasné, jakým způsobem zapisovat ty čísla trojkové soustavy pomocí přechodových stavů(neboli na druhou pásku)  :(

Ja som si to predstavoval tak, že to budem mať na druhej páske. Implementovať je to najjednoduchšie asi tak, že najnižšia cifra bude vľavo, t.j. druhá páska s číslom 10, t.j. v trojkovej 201 vyzerá nejako takto: L102R. (Asi je dobre mať tam aj nejakú ľavú a pravú zarážku?)

* T.j. po zmazaní x si nastavíme nejaký stav s1, ktorý mi hovorí, že treba inkrementovať. A budem mať aj nejaký stav, nazvime ho s0, ktorý znamená, že som úspešne zinkrementoval a znovu mám mazať x.

* V tom stave s1 posúvam hlavu na druhej páske ceľkom po ľavú zarážku a keď na ňu narazím tak zmením stav na s2. Stav s2 znamená, že som v procese inkrementácie a všetky cifry naľavo od miesta kde práve ukazuje druhá hľava sú dvojky.

* Keď som v stave s2, tak si prečítam políčok a potom:
a) Ak je to 0 zmením na 1, môžem zmeniť stav na s0. (Inkrementácia je hotová,)
b) Ak je to 1 zmením na 2, stav na s0.
c) Ak je to 2, tak sa musím posunúť o jedno doprava, stav nemením.
d) Ak je to pravá zarážka, tak to znamená, že mám číslo tvaru 22222.....2222. Namiesto pravej zarážky dám 1 a o 1 vpravo pravú zarážku. Prejdem do stavu s3, ktorí stroju hovorí, že sa má posúvať doľava a všetko meniť na 0, až kým nedosiahne ľavú zarážku. T.j. dostanem pásaku do stavu L000000....000001R. Potom môžem zmeniť stav na s0.

Znovu pripomeniem, že TS som sa učil dávno, t.j. detaily si budeš musieť domyslieť sám.

Tu som písal hlavne o tom ako inkrementovať, možno to budeš chcieť pomeniť nejako o trochu inak. (Napríklad v bode d neprejsť do s0, ale do stavu, v ktorom sa kontroluje, či na páske nezostali x-ká. Lebo bod d znamená, že som zatiaľ zmazal počet x-ov, ktorý je nejakou mocninou trojky.)

Veľa zdaru pri programovaní TS.

Skus dat pozor na to, ci spravne inkrementujes taketo cisla:
>> L22101R.
T.j. ked to zmenis na
>> L22201R
tak ci sa nezabudnes vratit a prepisat predosle 2-ky na 0:
>> L00201R

Ja som si vyskusal tie znejaky simulator TS, konkretne JFLAP: http://www.jflap.org/
("Instalacia" bola uplne bezbolestna, stiahol som subor jflap.jar a spustil.)

Vyskusal som si v tom spravit TS na tento problem, trochu som to testoval a funguje - mozes si to pozriet na screenshotoch, alebo aj spustit moj zdrojak a testovat na nejakych vstupoch, pripadne upravovat, ak si stiahnes ten JFLAP
http://ifile.it/81tmy2z/meron.zip

Na tom screenshote/v zdrojaku su:
Stavy nalavo (q5,q6,q7) pripravne - vyrobim L0R.
Stavy napravo (q1,q2,q3) pocitacie - mazem x a pocitam ich pocet na druhej paske.
Stavy dole (q8,q9,q4) testovacie - uz su vsetky x zmazane, tak testujem, ci spodna paska ma tvar L00....001R
(Predpokladam, ze sa ten moj navrh da povylepsovat - usetrit par stavou alebo prechodov.)







Tie obrazky predstavuju: Diagram turingovho stroja = TS02.png, +nejake simulacie, konkretne tam kde na paske je na zaciatku 10x (a zobrazeny je stav ked sa x-y zmazali a ide sa testovat ako vyzera cislo na paske) = TS02_sim10x.png a ked na paske je na zaciatku 9x (tiez je tu prichod do testovacieho stavu a potom prichod do akceptacneho stavu) = TS02_sim9x.png a TS02_sim9xaccept.png

P.S.
Z casov Tvojich postov sa da tipovat, ze si v inom casovom pasme ako ja ;-) Studujes v USA?