TS pre jazyk

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