Assignment 8

Automaton_Theory

陆一洲 5140309557

Problem 1

My subroutine: $$10^np_010^m10^k\vdash^*10^n1p_f0^m10^{m+k}$$ (PS: I don't know why there is an extra 1 in the statement of the problem 0 0
Here is my Turing Machine(TM):

	$0$	$1$	$b$
$q_0$		$(q_1,1,R)$
$q_1$	$(q_2,1,R)$
$q_2$	$(q_2,0,R)$	GO SUBROUTINE & RETURN $p_3$
$q_3$		$(q_4,1,L)$
$q_4$	$(q_4,0,L)$	$(q_1,0,R)$

Problem 2

$$\begin{align*} S\rightarrow& ARA\\ A\rightarrow& aA\mid\vdash A\mid p_iA\mid\epsilon\\ R\rightarrow& aRa\mid a0E1b\mid a1E0b\\ &\mid p_iaUp_jb\left(\forall\ \delta(p_i,a)=(p_j,b,R)\right)\\ &\mid cp_iaUbcp_j\left(\forall\ \delta(p_i,a)=(p_j,b,L)\right)\\ U\rightarrow& aUa\mid bUb\mid aEp_i\mid p_iEa\mid p_iEp_j\\ E\rightarrow& aEb\mid p_iEp_j\mid aEp_i\mid p_iEa\mid \vdash \end{align*}$$ where
$a,b,c$ denotes arbitary symbol in $\{0,1\}$;
$A$ generates arbitary strings;
$R$ generates wrong reverse strings before the move;
$U$ generates strings after the move;
$E$ generates arbitary symbol both on the left side and right side, which denotes the occurance of errors.