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

Question

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?

Answer 1

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.

Answer 2

$(\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.

Answer 3

Cute.

First, build an automaton that computes the product from left to right. Easy! Put a transition $\overrightarrow x \xrightarrow{\;y\;} \overrightarrow z$ whenever $x \cdot y = z$. There are three states $\{\overrightarrow a,\overrightarrow b,\overrightarrow c\}$ representing the three possible products. Start in a fourth state $\overrightarrow 1$ with $\overrightarrow 1 \xrightarrow{\;x\;} \overrightarrow x$ for all $x$. The final state is $\overrightarrow x$ if and only if the product of the input word from left to right is $x$.

Now let's build an automaton that computes the product from right to left. This one will be non-deterministic. How do we do that? Simple… To go in the other direction, just reverse everything: the arrows and the direction of the product.

Where we had before $\overrightarrow{x} \xrightarrow{\;y\;} \overrightarrow{x \cdot y\:}$, we now take $\overleftarrow{x \cdot y\:} \xleftarrow{\;x\;} \overleftarrow{y}$: when we consume the word from left to right, we go from a product to its right-hand factor. Or, in other words, $\overleftarrow{x} \xleftarrow{\;y\;} \overleftarrow{y \cdot x\:}$.

Add a disconnected node $\overleftarrow 1$ for the sake of the empty word. All nodes are initial.

Now we need to compute both paths together, so we take the product of the two automata: $(\overrightarrow{x_1}, \overleftarrow{x_2}) \xrightarrow{\;y\;} (\overrightarrow{z_1}, \overleftarrow{z_2})$ iff $\overrightarrow{x_1} \xrightarrow{\;y\;} \overrightarrow{z_1}$ and $\overleftarrow{x_2} \xrightarrow{\;y\;} \overleftarrow{z_2}$. Let the four states $(\overrightarrow 1, \overleftarrow x)$ be initial, and the four states $(\overrightarrow x, \overleftarrow x)$ be final. A word is recognized by this non-deterministic automaton iff its product from left to right and its product from right to left are the same $x$.

Answer 4

It seems that your main problem is utilising nondeterminism, so let me elaborate on that.

The basic idea the others utilise is that a nondeterministic machine can guess the final result.

Let us consider your small example $abc$ and Gilles' construction idea. The automaton "computing" the right-to-left product guesses the result in the beginning and verifies it. So there are three possibilities:

• Guess $a$: As the first symol is $a$, the rl-product of $bc$ must have been $a$ or $b$.
  • Guess $a$: As the second symbol is $b$, the last symbol must have been $b$.
    • (Guess $b$:) It is $c$, so don't accept.
  • Guess $b$: As the second symbol is $b$, the last symbol must have been $c$.
    • (Guess $c$:) It is indeed $c$, so we accept.
• Guess $b$: As the first symol is $a$, this is not possible, so don't accept.
• Guess $c$: As the first symol is $a$, the rl-product of $bc$ must have been $c$
  • (Guess $c$:) As the second symbol is $b$, the last symbol must have been $a$
    • (Guess $a$:) It is $c$, so don't accept.

As you can see, the NFA is able to guess and check every possible computation bottom-up. Because the accepted language is defined as the set of strings that is accepted by at least one run, all non-accepting runs on the input are ignored; the NFA "always guesses right".

Now it is easy for this NFA to remember its first choice until the end. If it accepts, it can compare the remembered symbol to the lr-product (deterministically) obtained in parallel (how language intersection relates to NFA is surely covered in Ullman/Hopcroft, and any other basic textbook).