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

Problem Detail: 

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?

Asked By : Mr. Ariel

Answered By : David Lewis

The first trick here is to think of the multiplication table as the transition table of an automaton $A$ with each state representing a letter in your multiplication table, but not worrying about acceptance yet. So the letters on the left and in the body of the table are actually states -- it would be more accurate to write them as $q_a, q_b, q_c$, but I won't. The letters across the top are inputs.

Then construct the automaton $A_T$ ("$T$" for transpose) for reverse multiplication by transposing $A$:

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

So $A(abc)$ takes you to state $c$, and likewise $A_T(cba)$ moves into state $a$ of $A_T$, as you note.

However, $A_T$ assumes you are going right-to-left, and we still want to go left-to-right. So the second trick is to reverse the automaton (not the multiplication, which would just get us back were we started), by reversing all the arrows, which leads to a non-deterministic automaton $A_{TR}$ given by the transition table below, with subsets indicated by concatenated letters to keep the chicken scratching down, so $ac$ is really $\{a,c\}$. (hope I got it all right -- seems to work).

$\qquad \displaystyle\begin{array}{c|ccc} A_{TR} & a & b & c \\ \hline a & ab & b & c \\ b & ∅ & c & a \\ c & c & a & b \\ \hline ab & ab & bc & ac \\ bc & c & ac & abc \\ ac & abc & ab & bc \\ abc & abc & abc & abc \\ ∅ & ∅ & ∅ & ∅ \end{array}$

You can interpret this as a non-deterministic automaton with only the three rows above the line or a determinized version with all 8 rows.

Finally, the machine to solve the problem is the cross-product automaton of the original $A$ and $A_{TR}$, that is $A \times A_{TR}$ to perform the intersection behavior of the two automata (we don't need $A_T$ any more). $A \times A_{TR}$ has states that are pairs like $\langle a,ac\rangle$. The transition function runs $A$ and $A_{TR}$ independently. A single start state $\langle 1,1 \rangle$ goes into $\langle a,a \rangle$ under input $a$, into $\langle b,b \rangle$ under input $b$, etc.

Accepting states in the non-deterministic version are $\langle a,a \rangle$ etc. In the deterministic version, accepting states are pairs in which the first component is $\in$ of the second component set, such as $\langle a,a \rangle$ or $\langle b,bc \rangle$.

$A \times A_{TR}$ augmented and determinized as shown has $25=3\cdot 8+1$ states, so forgive me if I don't write it out in detail. But the non-deterministic version has only $10=3\cdot 3+1$ states.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1467