Question

6. (10 pts) Is L regular? Either prove that it is not regular using pumping lemma, or describe an RE for it. The alphabet of the language is 10,1, +,-) L = { x = y + z | x, y, z are binary integers, and x is the sum of y and z }. For example, strings 1000 = 101 + 11, 0101 = 010 + 11, and 101 = 101 + 0 are in the language, but strings 100 = 101 + 10, 1 = 1 = 1,1 + 1 = 10, and 1111 are not in the language.

Answer 1

Here,

Σ = {0, 1, +, =} and

L = {x=y+z | x, y, z are binary integers}

** Caution: there must be one [=] and one [+] in any string in L, so the repeated string must be in one of the binary numbers. But, changing the term renders the equation wrong and changing the numbers added changes its sum, which is again incorrect.

Now, proving the Language L, is not regular using pumping lemma.

Definition of pumping lemma:

“If an infinite language has to be accepted by the finite automata, then there has to be some looping pattern(s) existing in the system which can generate all the finite strings of the language”

Let, L is regular and let p be its pumping length.

Let s=1^p+1=10^p+1^p. this equation is true so s belongs to L.

Now, |s|>=p, and by pumping lemma, s=xyz with |xy|<=p, |y|>0 and xz belongs to L(from the condition of pumping theorem ).

Again, since first p characters of s are all 1 and |xy|<=p, y must be made of 1s only.

So, xz=1^p-|y|=10^p+1^p. Since |y|>0, xz has a different string to left of [=] sign than that of s but is otherwise identical.

But, since the binary expansions are unique, the equation given by xz cannot be true.

Hence, xz doesn’t belongs to L, contradicting the pumping lemma and proving that L is not regular.