9
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Apr 23 '12 at 18:52

This question came from our site for theoretical computer scientists and researchers in related fields.

6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, it really helped me your answer to understand the idea behind of non determinism and the "reverse" of an automata. I was having problems understanding this concepts using the book of Hopcroft, rigth now I'm using the book of Sipser "Introduction to the Theory of Computation" its reall good. $\endgroup$ – Mr. Ariel Apr 25 '12 at 0:53
  • $\begingroup$ Consider the input $ba$. $\langle 1, 1 \rangle$ moves to $\langle b, b \rangle$ after input $b$, and then to $\langle c, \varnothing \rangle$ under input $a$, so $ba$ is not accepted, but should be? $\endgroup$ – cemulate Sep 16 '15 at 7:18
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice way to prove it with the formula -- upvote for that. As for the alternative "non-deterministic guess-and-verify" idea, that is usually OK for a proof, but is pretty tricky to actually carry out, as the problem requests. I think there are a lot of missing details here, such as how to keep track of the string form the back end. $\endgroup$ – David Lewis Apr 23 '12 at 23:57
  • $\begingroup$ @David, the details are missing on purpose. $\endgroup$ – Yuval Filmus Apr 24 '12 at 1:33
  • $\begingroup$ @Yuval -- he did not say it was homework -- we trust people here, correct? I also think this existence proof will result in quite a large machine, probably a lot larger than necessary. $\endgroup$ – David Lewis Apr 24 '12 at 4:27
  • $\begingroup$ @DavidLewis: Gilles gave a more complete answer which shows that the NFA is indeed not too big; nondeterminism does that for you. The corresponding DFA might be huge, though. $\endgroup$ – Raphael Apr 24 '12 at 5:54
  • $\begingroup$ @MohamedAbbas Perhaps, I'm not planning to check. $\endgroup$ – Yuval Filmus Nov 21 '15 at 14:11
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm having a bit of trouble grokking this. Don't you have to verify that $\overrightarrow{x} \xleftarrow{\;y\;} \overrightarrow{y \cdot x\:}$ leads to a finite state set? IAC, it's not just as simple as "reverse everything", since you still have to consume from left to right, but multiply from right to left, and I'm not sure you've done that. $\endgroup$ – David Lewis Apr 23 '12 at 23:52
  • $\begingroup$ @DavidLewis The state set is finite, I defined it to be $\{overleftarrow{a},\overleftarrow{b},\overleftarrow{b},\overleftarrow{1}\}$. I have reversed the order of the multiplication (barring more typos). $\endgroup$ – Gilles 'SO- stop being evil' Apr 23 '12 at 23:57
5
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ The idea of guessing an string was weird to me, but I have been reading the book of Sipser and I think that is a better aproach for newbies like me in the theory of computation. $\endgroup$ – Mr. Ariel Apr 25 '12 at 0:37
  • $\begingroup$ Think of guessing as forking with assumed input. But need to be careful with guessing strategies -- ensure that any storage needed for guessing is bounded uniformly for all forked threads, otherwise you don't have a finite-state automaton any more. Also, need a uniform bound on the number of forked threads active. I think Raphael's description here works, but it needs to be mentioned at least. $\endgroup$ – David Lewis Apr 25 '12 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.