Regularity of a language With pumping Lemma

Question

Interprete strings as numbers in Z ≥0 in binary (possibly with leading zeros, there is no modulo operation here). The following language over {0, 1} is regular {xyz : |x| = |y| = |z| and x + y = z}?

I think to prove the non regularity of this language, I should apply Pumping Lemma and show that there exists no possible setting such that all three conditions of pumping lemma are satisfied.

Answer 1

Consider the string (0^p)1(0^p)1(0^p-1)10 of length 3p + 3. This is a string in the language because choosing |x| = |y| = |z| means that x = (0^p)1, y = (0^p)1 and z = (0^p-1)10, and 1 + 1 = 10. Now, the pumping lemma says that this can be written as rst where:

• |rs| <= p
• |s| > 0
• r(s^k)t is in the language for all natural numbers k

Note that in our case, s must consist entirely of leading 0 from our component x. Suppose we choose k = 0. There are several cases to consider:

• |rt| is not evenly divisible by 3. In this case, the string cannot possibly be in our language since the condition |x| = |y| = |z| cannot be satisfied.
• if |rt| is evenly divisible by 3, consider our new x, y and z: we removed some number 3m of leading 0s. This means that |x| = |y| = |z| = p + 1 - m. The 1 originally at the end of our old x will be left-shifted by (m - 1) positions in the new string; the 1 at the end of y originally will be left shifted by (m - 2) positions in the new string; and the 1 at the end of z will remain at the second-to-last position in z.
  1. if m = 1, then y will no longer contain any 1 at all, so x + y + z cannot be satisfied
  2. if m > 1, then x will represent a number greater than or equal to 10 and y will represent a positive number. However, the sum of a number greater than or equal to 10 and a positive (non-zero) number cannot be equal to 10. So, x + y + z cannot be satisfied here either.

Therefore, there is no choice for m = |s| such that choosing k = 0 gives us r(s^k)t in the language. This is a contradiction and therefore our implied assumption that the language is regular must be false.