0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.