# Are these two languages regular?

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?

• What do you think? – Yuval Filmus Mar 4 '13 at 7:10
• I thing 1st one is regular where as second is non-regular. – 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?
• 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). – Hendrik Jan Mar 4 '13 at 17:20