Question $3$

Construct TMs in compositional tabular forms $($multitape and$/$or nondeterministic if necessary!$)$

that perform the following computations :

$($i$)(s,$#$w)|--*{*}_M(h,$#$w^R)$

$($ii$)(s,$#$w)|--*{*}_M(h,$#$ww)$

$($iii$)(s,$#$w)|--*{*}_M(h,$#$w$#$w^R)$

$($iv$)(s,$#$w)|--*{*}_M(h,$#$a^n{b}^n)$ where the number of as and $bs$ in $w$ are both equal to a fixed

integer $n>0.$