Fórum studentů MFF UK

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

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

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.

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

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

Fórum studentů MFF UK

TS pre jazyk

TS pre jazyk

Re: TS pre jazyk

Re: TS pre jazyk

Re: TS pre jazyk