Question

Use the pumping lemma to prove that the following languages are not regular.

(a)L2 = {y = 10 × x | x and y are binary integers with no leading 0s, and y is two times x}. (The alphabet for this languages is {0, 1, ×, =}.) For example, 1010 = 10 × 101 is in L2, but 1010 = 10 × 1 is not.

(b)Let Σ2 = {[ 0 0 ] , [ 0 1 ] , [ 1 0 ] , [ 1 1 ]} . Consider each row to be a binary number and let L3 = w ∈ Σ ∗ 2 | the bottom row of w is the square of the top row of w . For example, [ 0 1 ] [ 0 0 ] [ 1 0 ] [ 0 0 ] [ 0 0 ] ∈ L3, but [ 0 1 ] [ 0 0 ] [ 0 0 ] [ 1 0 ] [ 0 0 ] [ 0 0 ] ∈/ L3.

Answer 1

The pumping lemma states that any regular language L has a pumping length p such that all strings of length greater than p can be divided into three parts x, y and z such that

• 
• 
• 

(a) Let w be a string belonging to L2 such that the length of w is greater than its pumping length. Then w=x.y.z. The cross sign must belong to either of x, y or z.

• Suppose the cross belongs to x. Then the whole of y lies in the number on the right. The number on the left was initially 10 times the number on the right, however pumping y to w will change the number on the right so the relation will no longer hold. Hence the cross does not belong to x.
• Suppose the cross belongs to y. Then on pumping y to w, the number of cross signs will increase. But all strings in L2 must have only one cross. Hence the cross does not belong to y.
• Suppose the cross belongs to z. Then the whole of y lies in the number on the left. The number on the left was initially 10 times the number on the right, however pumping y to w will change the number of the left so the relation will no longer hold. Hence the cross does not belong to w.

So we have proved that w cannot be written as w=xyz were they satisfy the given criteria. Hence L2 is not a regular language.