Effective formal algorithm for computing GCD Hello everybody I am currently so stuck at solving this problem in the first Volume of The Art of Computer Programming: 
[M25] Give an "effective" formal algorithm for computing the greatest common divisor of positive integers $m$ and $n$, by specifying $\theta_j$, $\phi_j$, $a_j$, $b_j$ as in Eqs. (3). Let the input be represented by the string $a^mb^n$, that is, $m$ $a$'s followed by $n$ $b$'s. Try to make your solution as simple as possible. [$Hint$: Use Algorithm E, but instead of division in step E1, set $r \leftarrow |m-n|$, $n \leftarrow min(m,n)$.]
Now this is the part related to Eqs. (3):
Let $A$ be a finite set of letters, and let $A^*$ be the set of all strings on $A$ (the set of all ordered sequences $x_1x_2...x_n$, where $n \ge 0$ and $x_j$ is in $A$ for $1 \le j \le n$). The idea is to encode the states of the computation so that they are represented by strings of $A^*$. Now let $N$ be a nonnegative integer and let $Q$ be the set of all $(\sigma,j)$, where $\sigma$ is in $A^*$ and $j$ is an integer, $0 \le j \le N$; let $I$ be the subset of $Q$ with $j=0$ and let $\Omega$ be the subset with $j=N$. If $\theta$ and $\sigma$ are strings in $A^*$, we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form  $\alpha\theta\omega$ for strings $\alpha$ and $\omega$. To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta_j$, $\phi_j$ and the integers $a_j$, $b_j$ for $0 \le j < N$:
$f(\sigma,j)=(\sigma, a_j)$ if $\theta_j$ does not occur in $\sigma$;
$f(\sigma,j)=(\alpha\phi_j\omega,b_j)$ if $\alpha$ is the shortest possible string for which $\sigma=\alpha\theta_j\omega$;
$f(\sigma,N)=(\sigma,N)$. $(3)$ 
And finally this is the Algorithm E:
Algorithm E $(Euclid's \, algorithm)$. Given two positive integers $m$ and $n$, find their $greatest \, common \, divisor$, that is, the largest positive integer that evenly divides both $m$ and $n$.
E1. [Find remainder] Divide $m$ by $n$ and let $r$ be the remainder. (We will have $0 \le r < n$.) 
E2. [Is it zero?] If $r=0$, the algorithm terminates; $n$ is the answer. 
E3. [Reduce] Set $m \leftarrow n, \, n \leftarrow r$, and go back to step E1. 
I am really happy and I appreciate anyone who comes by and help me because I've spent hours without success in finding the suitable parameters. Thank you StackExchange.
 A: Eqs. (3) seems to define a machine that do the followings:


*

*Operation steps are numbered by $j$.

*In step $j$, the machine detects the first occurrence of $\theta_j$ in $\sigma$,  and replaces $\sigma = \alpha\theta_j\omega$ by new $\sigma=\alpha\phi_j\omega$. Then go to step $b_j$.

*If $\theta_j$ does not presence, then go to step $a_j$.



My solution
Assume the input is $(\underbrace{a...a}_m\underbrace{b...b}_n, 1)$ and let $\epsilon\in A^*$ denote the empty string. My plan is as  the following:
Step 1.
Detect ab in $\sigma$ and replace ab by ab (ie, no replacement). Then go to step 2.
If ab does not presence in $\sigma$, then go to step 4.
Step 2.
Replace the first occurance of a by ca. That is, append a c before the first a.
It is impossible that there is no a in $\sigma$, because we are from step 1. So we go to step 3 directly.
Step 3.
Delete ab in $\sigma$, and then go to step 1.
Again, it is impossible that there is no ab in $\sigma$.

So far, the modified first step of Algorithm E is implemented. The steps are encoded in the table:
$$\begin{array}{|c|c|c|c|c|}
\hline
j & \theta_j & \phi_j & a_j & b_j        \\ \hline
1 & ab       & ab     & 4   & 2          \\ \hline
2 & a        & ca     & \text{any} & 3   \\ \hline
3 & ab     & \epsilon & \text{any} & 1   \\ \hline
4 & ...      & ...    & ... & ...        \\ \hline
\end{array}.$$
For example:
$(aaaaa\,bb, 1)\to (aaaaa\,bb, 2)\to (c\,aaaaa\,bb, 3)\\
\to (c\,aaaa\,b, 1)\to (c\,aaaa\,b, 2)\to (cc\,aaaa\,b, 3)\\
\to (cc\,aaa, 1)\to (cc\,aaa, 4)\to ...$
Observe that $a^5b^2$ becomes $c^2a^{5-2}$. These steps can also transform $a^2b^5$ into $c^2b^{5-2}$
In steps 4-? we transform $c^mb^n$ or $c^na^m$ to the original form $a^mb^n$ so that we can apply steps 1-3 again and again.

Step 4.
Detect cb. If cb exists in $\sigma$ then we know that $\sigma$ is of the  form $c^mb^n$. Go to step 5. 
If there is no cb, then go to step 6.
Step 5.
We have to replace c by a repeatedly. So we detect c and replace it by a, and then go to step 5 again.
If there is no c remaining, then we can go to step 1.
Step 6.
Detect ca. If ca exists in $\sigma$ then we know that $\sigma$ is of the form $c^na^m$. Go to step 7.
If there is also no ca, then there are only c in $\sigma$. Go to step 10 and terminate the process.
Step 7.
We have to detect c and then append b in the end of $\sigma$. If c is detected, go to the next step to append b.
If there is no c remaining, then we can go to step 1.
Step 8.
Replace a by ab, ie, append a b after a. Then go to step 9.
Step 9.
Remove the leading c and go bacj to step 7 to check for remaining c again.
Step 10.
There are only some c in $\sigma$. The length of cs is the g.c.d. Note that $N=10$ in this algorithm.
$$\begin{array}{|c|c|c|c|c|}
\hline
j & \theta_j & \phi_j & a_j & b_j        \\ \hline
4 & cb       & cb     & 6   & 5          \\ \hline
5 & c        & a      & 1   & 5          \\ \hline
6 & ca       & ca     & 10  & 7          \\ \hline
7 & c        & c      & 1   & 8          \\ \hline
8 & a        & ab     & \text{any} & 9   \\ \hline
9 & c      & \epsilon & \text{any} & 7   \\ \hline
10& -        & -      & -   & -          \\ \hline
\end{array}.$$
