Words that have the same right- and left-associative product

I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting:


Give a non deterministic finite automaton accepting all the strings that
have the same value when evaluated left to right as right to left by
multiplying according to the following table:


$\qquad \displaystyle\begin{array}{c|ccc}
\times & a & b & c \\
\hline
a & a & a & c \\
b & c & a & b \\
c & b & c &a
\end{array}$

So if we have the string $abc$,

the product from left to right is $(a \times b) \times c=a \times c=c$ and

the product from right to left is $a \times (b \times c)=a \times b=a$

So $abc$ should not be acceptable for the automata. To me its obvious that any string $aa^$ or $bb^$ or $cc^*$ is an aceptable string (their right and left evaluation work on the same partial strings). It is easy to give an NFA that describes the left to right evaluation but the problem is that if the machine try to compute the right to left evaluation I think it needs to know the length of the string (so infinite memory is necessary).

So how can a non deterministic automata evaluate from right to left in order to compare with the left to right evaluation?

$(\ast)$ If $L$ is a regular language, then $L^R$, the language consisting of the reverse of all words in $L$, is also regular. Take this as an exercise.

How does this help us solve the problem? Let $L_a,L_b,L_c$ be the languages consisting of all strings that evaluate to $a,b,c$ when evaluating from left to right. The language you're interested in is
$$ (L_a \cap L_a^R) \cup (L_b \cap L_b^R) \cup (L_c \cap L_c^R). $$
This shows that if you know how to prove $(\ast)$, then you can construct an NFA for the language in question.

In fact, if you use the idea of the proof of $(\ast)$, then you can probably just go ahead and construct the automaton. So let's consider this. In particular, let's try to construct an NFA for $L_a^R$, the language of all strings that evaluate to $a$ when evaluated from right to left.

The idea is this. Suppose that the first letter you see is $b$. Then the rest of the string must evaluate to $b$ (since $bx = a$ implies $x = b$). Similar reasoning applies when the first letter is $c$. When the first letter is $a$, however, the rest can evaluate to either $a$ or $b$, or be null. With an NFA, we can guess (and later verify our guess).

This hint should give you enough to think about, and hopefully solve the problem.

StackExchange Computer Science Q#1467, answer score: 8