Let an automaton $A$ sit on point $O$ $(0,0)$ and turned to the North. That automaton can execute only any combination of three different commands in each step:
- Move one unit forward
- Turn 90 degrees clockwise
- Turn 90 degrees counterclockwise
Let $\Sigma = \{F, R, L\}$ represent the mentioned commands. Now, $w$ is a word in $\Sigma^*$ with a routine that the automaton will execute indefinitely.
Example: $w =$ 'F'
at step 0, A is on (0,0) pointing to North
at step 1, A is on (0,1) stil pointing to North
...
$w =$ 'FL'
at step 0, A is on (0,0) pointing to North
at step 1, A is on (0,1) pointing to West
at step 2, A is on (-1,1) pointing to South
at step 3, A is on (-1,0) pointing to East
at step 4, A is on (0,0) pointing to North (again)
Question: Given $w$, decide if the $A$ will be stuck in a cycle.
I can intuitively answer that question, but I cannot formalize:
If after step 1, $A$ is on $(0,0)$ or pointing to West, South, or East, then $A$ is in a cycle.
Suppose that after step 1, for any $w$, $A$ is at $(a, b)$. Let $S$ a sequence of positions that $A$ takes in each step, $S = \{s_0, s_1, s_2, s_4, \ldots \}$, $s_0 = (0,0)$, $s_1 =(a,b)$. Let $u$ be the vector $(a,b)$ and $f$ be a function of rotation relative to initial orientation to final orientation after $w$. Finally, let $w = f(u)$. Then
\begin{array} ss_1 = s_0 + u, \\ s_2 = s_0 + u + w, \\ s_3 = s_0 + u + w + f(f(u)) , \\ s_4 = s_0 + u + w + f(f(u)) + f(f(w)), \end{array}
If $f$ is a 90 degrees rotation (clockwise or counterclockwise) then $f(f(u)) = -u$. If $f$ is a 180 degrees rotation then $f(u) = -u$. In such cases,
\begin{array} ss_4 = s_0 \end{array}
therefore, $A$ only "escapes" if:
f is the identity rotation
u != (0,0)
To verify whether $f$ is the identity rotation, the number of 'L' commands in $w$ should be equal to the number of 'R' commands.
Let initial state be $P_0=(0,0,N)$ and $P_1=(a,b,X)$ be the state after step 1. Then:
If $P_1=(0,0,X)$ then $A$ will stay forever at its starting point.
If $P_1=(a,b,E)$ then $A$ underwent a counterclockwise rotation of $90°$ about center $\displaystyle C=\left({a-b\over2},{a+b\over2}\right)$. Thus after 4 repetitions $A$ is back to start.
If $P_1=(a,b,W)$ then $A$ underwent a clockwise rotation of $90°$ about center $\displaystyle C=\left({a+b\over2},{a-b\over2}\right)$. Thus after 4 repetitions $A$ is back to start.
If $P_1=(a,b,S)$ then $A$ underwent a rotation of $180°$ about center $\displaystyle C=\left({a\over2},{b\over2}\right)$. Thus after 2 repetitions $A$ is back to start.
If $P_1=(a,b,N)$ then $A$ underwent a translation by vector $(a,b)$. Thus it will never return to starting point, unless $(a,b)=(0,0)$.