TS pre jazyk

TS pre jazyk

Příspěvekod anonym123 » 19. 1. 2011 02:43

Popiste TS pro jazyk 1^k01^{k^2}.

Poradte niekto prosim, nejak na to nemozem prist. Vopred dakujem.
anonym123
 

Re: TS pre jazyk

Příspěvekod bishop » 19. 1. 2011 09:30

Doporucuji ho popsat jako dvou-paskovy:
- na prvni pasce nechas vstup
- na druhou pasku okopirujes k jednicek
Potom uz ti staci prochazet vstup a vzdy smaznout na leve strane jednicku a na prave strane k jednicek (ty mas ulozene na druhe pasce) a toto opakujes nez ti zbyde 0.
bishop
Matfyz(ák|ačka) level I
 
Příspěvky: 6
Registrován: 16. 1. 2008 11:24
Typ studia: Informatika Bc.

Re: TS pre jazyk

Příspěvekod anonym123 » 19. 1. 2011 11:23

Dakujem, presne to napadlo aj mne ked som zaspaval, este keby si napisal jeden prechod, aby som videl, ako sa to zapisuje, ked mas viac pasok, tak by to bolo skvele ;)
anonym123
 

Re: TS pre jazyk

Příspěvekod H-anonym » 19. 1. 2011 18:07

Na strane 5 skript mas definici k-paskovyho stroje... je tam i definice prechodove unkce

\delta : Q \times \Sigma^k \rightarrow Q \times \Sigma^k \times \{R,N,L\}^k \cup \perp

Takze "instrukce" prechodove funkce ma zhruba tvar (stav, pismeno pod hlavou 1, pismeno pod hlavou 2, ... pismeno pod hlavou k \rightarrow stav, nove pismeno pod hlavou 1, ... nove pismeno pod hlavou k, pohyb hlavy 1, ... , pohyb hlavy k

konkretne treba (q_0, 1, 1, 0) \rightarrow (q_{10}, 0, 1, 0, L, R, N) pro 3 pasky
H-anonym
 


Zpět na NTIN090 Základy složitosti a vyčíslitelnosti

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron