Let $\operatorname{value}(x)$ be the result when the symbols of $x$ are multiplied from left to right according to

$\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}$

Is $L=\{xy \mid |x|=|y| \land \operatorname{value}(x) = \operatorname{value}(y)\}$ regular?

Is $L=\{xy \mid \operatorname{value}(x)= \operatorname{value}(y)\}$ regular?

  • 2
    $\begingroup$ What do you think? $\endgroup$ – Yuval Filmus Mar 4 '13 at 7:10
  • $\begingroup$ I thing 1st one is regular where as second is non-regular. $\endgroup$ – gopu Mar 4 '13 at 7:16

Hint for (1): consider a different type of value, $\mathrm{value}(s) = 1$ if $s$ ends with $z$, and $\mathrm{value}(s) = 0$ otherwise. Define the language $L$ as in your case, and consider $L \cap x^* z y^* z$.

Hint for (2): consider the language $L_\alpha = \{xy : \mathrm{value}(x) = \mathrm{value}(y) = \alpha \}$. What is the relation between $L_\alpha$ and $M_\alpha = \{ x : \mathrm{value}(x) = \alpha \}$? Is $M_\alpha$ regular?

  • $\begingroup$ Nice hints! (1) still needs hard work to find a good $xy$ that fails when the middle is 'shifted'. (2) I almost had the impression that two parts with the same evaluation was equivalent to the final evaluation $a$ because of the diagonal. Alas: the multiplication is not associative. (to avoid misunderstanding, this does not harm your solution). $\endgroup$ – Hendrik Jan Mar 4 '13 at 17:20

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.