Gcd is a Regular Language

Question

Show that GCD = {z|z = gcd(x,y), where x, y are binary numbers} is a regular language. [Hint: There is an algorithm that deals with 0s and 1s for this problem.]

Answer 1

The language $L =\{(a,b,c) |\, a = \gcd(b,c)\}$ where strings are binary representations is not regular.

Let $p$ be the pumping constant of the pumping lemma. Choose a string $(a_0, b_0, c_0) \in L$ such that $|a_o| \ge p$. Then it can be decomposed $a_0 = a_x a_y a_z$ where $|a_x a_y| \le p$ and $|a_y| \ge 1$ and $\forall n, (a_x a_y^n a_z , b_0, c_0) \in L$.

But for $n$ large enough, the front part of the triple can no longer be the gcd since it grows even bigger than $b_0$ and $c_0$.