Specify a decisive Turing machine that calculates the following function $f$.

Question

Specify a decisive Turing machine that calculates the following function $f$: $$\small f:\{a,b\}^*\to\{a,b\}^*\textrm{ with } f(w)= \begin{cases} (bba)^{3\cdot\#_b(w)}& \text{if } \#_a(w) \text{ not devidable by }4\\ \text{undefined} & \text{otherwise.} \end{cases}$$ where $\#_b(w)$ is the amount of $b$'s in $w$.

Let $M=(K,\Sigma,\Gamma,\delta,s,F) \text{ with } s\in K$ initial state where $K$ is the set of states; $\Sigma$ is the alphabet; $\Gamma$ is the infinite tape; $F\subseteq K$ are final states and $\delta:K\times\Gamma\to K\times \Gamma \times \{R,N,L\}$ is the transition function with ($R$=right, $L$=left, $N$=neutral).

I have no clue how to go on and design the TM in order to calculate $f$. Can you give me some hints?

Answer 1

Hint: We need 4 states $s_0,\dots, s_3$ to track $\#_a(w)$ mod $4$, such that only $s_0$ is not final, and we have to output $bbabbabba$ whenever we meet letter $b$.