Matematické Fórum

martinko18

Ahojte, potreboval by som pomoc s tymto prikladom Turingoveho stroja:

-mam ho navrhnut, zapisat prechodovu funkciu
-urobit hociaky priklad pre ukazku vypoctu na tomto stroji

zle napisane, spravne ma byt: $\{a^{i+j}c^j|i>0\}$

- poprosim aj komentar co a ako jednotlive vypocty prebiehaju

Kondr · 07. 06. 2009 19:50

Má to být $\{a^{i+j}c^j|j>i>0\}$ nebo $\{a^{i+j}c^j|i>0\}$ ? To co jsi napsal nedává smysl.

martinko18

Myslim, ze tato druha moznost $\{a^{i+j}c^j|i>0\}$
(som odpisoval rychlo zadanie, tak som sa sekol, ale myslim, ze takto to ma byt)

Kondr · 07. 06. 2009 20:56

↑ martinko18:Nejdřív bych udělal tři stavy, který zkontrolují, že je slovo tvaru $a^kc^j$ . První z nich bude počátečním stavem automatupokud se v něm načte a, zůstane se ve stejném stavu, pokud načte c, skočí do druhého stavu, pokud konec pásky, skočí do třetího, pro cokoliv jiného do zamítajícího stavu. Hlava se v tomto stavu vždy posouvá doprava. Druhý stav - s načtením c-čka zůstáváme ve druhém stavu, s načtením konce pásky jdeme do třetího stavu, s čímkoliv jiným zamítáme. Z počátečního stavu se tedy v konečném počtu kroků dostaneme buď do zamítajícího, nebo do třetího. Pokud jsme ve třetím (tj. jsme na konci řetězce, který je tvaru $a^kc^j$ ; zbývá ověřit k>j, tj. i>0) budeme dělat vždy toto: najdeme poslední c, změníme ho na b, najdeme poslední a, změníme ho na b, posuneme se na konec řetězce a vvrátíme se tak do třetího stavu. Pokud se nám už nepodaří najít c, ověříme, že jsme schopní najít a. Pokud ano, přimeme, pokud ne, zamítneme. Rozepisování algoritmu do přechodové funkce je děsná nuda, když to uděláš a napíšeš výsledek, tak ti ho možná někdo zkontroluje. Pokud ti to nepůjde, n Pokud se nám c podaří najít a a ne, zamítneme. apiš, kde ses zasekl.

martinko18 · 07. 06. 2009 21:08

Zatial dakujem velmi pekne za pomoc, vyskusam to, len asi az zajtra, lebo este musim nastudovat konecne a zasobnikove automaty, potom sa vrhnem na toto.

martinko18 · 09. 06. 2009 20:40

Ja som to skusil takouto cestou, moze byt?

xxsawer · 09. 06. 2009 23:30

↑ martinko18:

Tak tohle se mi vůbec nezdá...moh bys napsat co to má konkrétně dělat a jak to funguje???
Jestli to chápu dobře tak ten TS měl přijímat jazyk generovaný tímhle výrazem:
$\{a^{i+j}c^j|i>0\}$

martinko18

↑ xxsawer:

Ano, ten TS by mal prijimat jazyk generovany tym vyrazom, a to je napr. aaaaccc, ... Myslim, ze by to ta moja schema mala zhltnut.
Princip som dal taky, ze nacita prve a, prepise ho na A, ostatne a preskoci a najde c, to prepise na C, vrati sa spat ku nasledujucemu a a zmeni za A a opakuje to, nejak tak som to myslel, az na koniec oznaci posledne A, prejde oznacene C-cka a skonci na blenk. Asi tak, neviem, ci je to dobre :-(

xxsawer · 10. 06. 2009 00:01

↑ martinko18:

Princip vypadá dobře :) Jenom nevim jestli to je formálně podle definice TS, ty tam totiz delas v jednom kroku vzdycky dva ukony. Vzdycky neco zapisujes na pasku a navic posouvas hlavu. Prechodova funkce je definovaná tak, že se na základě stavu a obsahu pásky pod čtecí hlavou rozhoduješ jestli:
-zapíšeš něco na pásku
-posuneš hlavu doprava
-posuneš hlavu doleva

Ale jestli jste si to ukazovali takhle tak to nech...

martinko18

↑ xxsawer:

aj inym sposobom sa to da zapisat, ak to myslis, ja som pouzil tento graficky a tam toho menej znacime, aspon tak sme to prebrali, ale to je jedno, len dufam, ze to bude fakcit

Kondr · 10. 06. 2009 16:52

Zapisovat to takto graficky je OK, akorát by mělo z každého vrcholu vést tolik šipek, kolik je symbolů abecedy. A připadá mi, že to nefunguje ani na tom zmíněném slově aaacc.

xxsawer · 10. 06. 2009 17:48

↑ Kondr:

Nene z kazdyho stavu urcite tolik sipek kolik je symbolu ve vstupni abecedy vest nemusi. Tohle neni konecnej automat...
Kdybys tomu chtel dat na vstup dejme tomu accdfdas tak tam proste ten prechod bude chybet a TS ten retezec neprijme...

no_-_name · 11. 05. 2012 00:04

Teď se s prominutím přihlásím já, mírně zmaten. Hledám TS, který pracují s abecedou {0,1} a dokáže na pásce otočit pořadí znaků ve vstupním řetězci a pak ještě jeden se shodnou abecedou a dokáže v řetězci nul a jedniček nahradit všechny nuly dvěma jedničkami.

Ten první vůbec nevím jak rozlousknout a ten druhý mám již nakreslený, postupuju tak, že v počátečním stavu jdu o krok vlevo a označím si první prázdné místo, pak jdu na konec řetězce doprava a pokud je tam nula, napíšu jedničku a jdu o krok vpravo (dejme tomu stav Q1). Tam je momentálně prázdno a to přepíšu taky na 1. Poté se vracím vlevo až k nějaké nule a pokračuju opět stavem Q1. Problém je v tom, že po stavu Q1 už teď prázdno není a tak zbytečně přepisuju už existující jedničku a na konci mi jedna chybí...

Matematické Fórum

#1 07. 06. 2009 19:28 — Editoval martinko18 (07. 06. 2009 20:47)

Turingov stroj - prosim o pomoc s prikladom

#2 07. 06. 2009 19:50

Re: Turingov stroj - prosim o pomoc s prikladom

#3 07. 06. 2009 20:39 — Editoval martinko18 (07. 06. 2009 20:48)

Re: Turingov stroj - prosim o pomoc s prikladom

#4 07. 06. 2009 20:56

Re: Turingov stroj - prosim o pomoc s prikladom

#5 07. 06. 2009 21:08

Re: Turingov stroj - prosim o pomoc s prikladom

#6 09. 06. 2009 20:40

Re: Turingov stroj - prosim o pomoc s prikladom

#7 09. 06. 2009 23:30

Re: Turingov stroj - prosim o pomoc s prikladom

#8 09. 06. 2009 23:42 — Editoval martinko18 (09. 06. 2009 23:44)

Re: Turingov stroj - prosim o pomoc s prikladom

#9 10. 06. 2009 00:01

Re: Turingov stroj - prosim o pomoc s prikladom

#10 10. 06. 2009 00:13 — Editoval martinko18 (10. 06. 2009 00:13)

Re: Turingov stroj - prosim o pomoc s prikladom

#11 10. 06. 2009 16:52

Re: Turingov stroj - prosim o pomoc s prikladom

#12 10. 06. 2009 17:48

Re: Turingov stroj - prosim o pomoc s prikladom

#13 11. 05. 2012 00:04

Re: Turingov stroj - prosim o pomoc s prikladom

Zápatí