Proving irregularity of a language

Question

While learning about formal languages, I found the following problem:

Let us consider words over the alphabet $\lbrace 0, 1\rbrace ^3$. We say that a word $\langle a_1, b_1, c_1 \rangle \ldots \langle a_n, b_n, c_n \rangle$ of length $n$ represents multiplication if the number whose binary representation is $c_1c_2 \ldots c_n$ equals the product of binary numbers $a_1a_2 \ldots a_n$ and $b_1b_2 \ldots b_n$. For example, $\langle 0, 0, 1 \rangle \langle 1, 0, 0 \rangle \langle 0, 1, 0 \rangle \langle 0, 0, 0 \rangle$ stands for multiplication $(4 \cdot 2 = 8)$. Prove that the language that consists of such words is not regular.

I have tried to solve this with the pumping lemma, yet apparently I cannot come up with a suitable word $w$, for which it will be easy to show that neither of its decompositions meets the lemma conditions. Could anyone lend me a hand?

Answer 1

If $p$ is the pumping length, let

$$w=\langle 0,0,1\rangle^p\langle1,1,1\rangle\langle 0,1,0\rangle^p\;,$$

representing $2^p(2^{p+1}-1)=2^{2p+1}-2^p$, or in binary

$$1\underbrace{00\dots00}_p\cdot\underbrace{11\dots11}_{p+1}=\underbrace{11\dots11}_{p+1}\underbrace{00\dots00}_p\;.$$

Pumping up doesn’t change the factors, but it does change the supposed product.

Answer 2

Consider the multiplication $2^n \cdot 2^n = 2^{2n}$ for large $n$. After pumping $m$ zeros the word will be $2^{n+m} \cdot 2^{n+m} = 2^{2n+m}$ which is false.