1
$\begingroup$

Given the following multiplication table how could one construct an NFA such that it accepts all strings that have a certain product (say a) ?

The string "abcb" would be evaluated as (a(b(cb))) = a

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

I tried to take the transpose of the above matrix:

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

And build an NFA for that. I then reversed all the transitions, but I don't think that works.

$\endgroup$
1
$\begingroup$

Start by checking that you would be able to build such a NFA if the multiplication table was associative. That would be a good starting point for you to work on. (If it's associative, the problem becomes very easy.) Once you've done that, the next step is:

Now to accommodate the fact that the multiplication table is in fact not associative, and that you want to group multiplications on the right first, you can use the ideas from Louis's comment. That should make it pretty easy for you to work out an answer to your own exercise, by yourself.

$\endgroup$

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.