why is this computational method by Knuth "effective" and "powerful"?
It's necessary to have some restriction such as "$\alpha$ is shortest possible string for which $\sigma = \alpha \theta_j \omega$" so the algorithm is unambiguous, because it's possible for $\theta_j$ to appear at multiple locations in $\sigma$.
After seeing Knuth's answer to exercise 1.1.8, I see how something like $x^k$ can be computed this way. Below is my rather cumbersome approach.


Let $A = \{a,b,c,d,e,t\}$ and $N=10$. 

Given $x,k$ where $x&gt;0$ and $k \ge 0$, the input will be $a^xb^k$ ($2^3$ would have input $aabbb$), and output will be the string $c^{x^k}$ ($x^k$ number of $c$'s. empty string denotes 1).

\begin{array}{cccccc}
j &amp; \theta_j &amp; \phi_j &amp; b_j &amp; a_j &amp; \text{comments}\\
0 &amp; b &amp; (\text{empty}) &amp; 1 &amp; 9 &amp; \text{remove one $b$. if no $b$, done.} \\
1 &amp; c &amp; c &amp; 3 &amp; 2 &amp; \text{if first time (no $c$'s), add $c$. else expand} \\
2 &amp; a &amp; tc &amp; 2 &amp; 8 &amp; \text{add a $c$ for each $a$} \\
3 &amp; a &amp; t &amp; 4 &amp; 6 &amp; \text{for each $a$, add in $c$ amount of $d$'s} \\
4 &amp; c &amp; ed &amp; 4 &amp; 5 &amp; \text{for each c, add in a $d$} \\
5 &amp; e &amp; c &amp; 5 &amp; 3 &amp; \text{change $e$ back to $c$} \\
6 &amp; c &amp; (\text{empty}) &amp; 6 &amp; 7 &amp; \text{clean up. remove all $c$'s} \\
7 &amp; d &amp; c &amp; 7 &amp; 8 &amp; \text{clean up. change all $d$'s back to $c$'s}\\
8 &amp; t &amp; a &amp; 8 &amp; 0 &amp; \text{clean up. change $t$'s to $a$'s}\\
9 &amp; a &amp; (\text{empty}) &amp; 9 &amp; 10 &amp; \text{remove all $a$'s. return}
\end{array}