Given $\Sigma = \lbrace 0, 1 \rbrace$ and $L \subseteq (\Sigma \times \Sigma \times \Sigma)^*$. Let $first(w), second(w), third(w)$ be word from $(\Sigma \times \Sigma \times \Sigma)^*$ limited to first column, second and third. From example for word $w = <0,1,1><1,1,1> <0,0,1>$ $first(w) = 010, second(w) = 110$ and $third(w) = 111$.
I define multiplication relation $R = \lbrace <a,b,c> |\ ab = c \rbrace$. Formal definiton of $L= \lbrace w \in (\Sigma \times \Sigma \times \Sigma)^* \ | \ R( bin(first(w)), bin(second(w)), bin(third(w)) \rbrace$ where $bin(w)$ is value of binary number represented by $w$ (f.e. bin(1101) = 1+4+8).
I need to show that $L$ is regular or not. Any ideas? Is an exercise clear? I can show that $L$ is regular with addition relation but it's too hard with multiplitaction.
The language $L$ is not regular. One can obtain this result by encoding the fact that $(2^n - 1)(2^n + 1) = 2^{2n} -1$. More precisely, let us write these three numbers in binary by a word of length $2n$, that is $2^n -1 \to 0^n1^n$, $2^n +1 \to 0^{n-1}10^{n-1}1$ and $4^n -1 \to 1^{4n}$. Then $$ \begin{pmatrix}0\\ 0\\ 1\end{pmatrix}^{n-1}\begin{pmatrix}0\\ 1\\ 1\end{pmatrix}\begin{pmatrix}1\\ 0\\ 1\end{pmatrix}^{n-1}\begin{pmatrix}1\\ 1\\ 1\end{pmatrix} \in L $$ Suppose that $L$ is regular. Then the language $$ L \cap \begin{pmatrix}0\\ 0\\ 1\end{pmatrix}^*\begin{pmatrix}0\\ 1\\ 1\end{pmatrix}\begin{pmatrix}1\\ 0\\ 1\end{pmatrix}^*\begin{pmatrix}1\\ 1\\ 1\end{pmatrix} = \left\{ \begin{pmatrix}0\\ 0\\ 1\end{pmatrix}^k\begin{pmatrix}0\\ 1\\ 1\end{pmatrix}\begin{pmatrix}1\\ 0\\ 1\end{pmatrix}^k\begin{pmatrix}1\\ 1\\ 1\end{pmatrix} \mid k \geqslant 0 \right\} $$ would be regular, but this language is not regular (for instance, by the pumping lemma).