TS pre jazyk

anonym123

TS pre jazyk

Příspěvek od anonym123 »

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

Poradte niekto prosim, nejak na to nemozem prist. Vopred dakujem.
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ěvek od bishop »

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.
anonym123

Re: TS pre jazyk

Příspěvek od anonym123 »

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 ;)
H-anonym

Re: TS pre jazyk

Příspěvek od H-anonym »

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
Odpovědět

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