Prove that the language mult is not a regular language as de

Prove that the language \'mult\' is not a regular language (as described above). Please be as detailed as possible.

0690809 Consider the alphabet 1 We shall use strings in this alphabet to describe three integers: one for the top row of bits, one for the middle row and one for the bottom row. Each integer is represented in binary For example, to represent the three integers 5, 7 and 35 (whose binary representations are 101, 111 and 100011, respectively), we use the string 0o111 (Note that we add 0\'s at the left end of the binary representations of the numbers in order 0 0 to pad them so that all three rows are of the same length.) Let MULTbe the language of all strings that represent correct binary multiplications, i.e, where the number represented by the third row is the product of the numbers represented 1 1S in in the first two rows. For example, the string 0 1 MULT, since 5 × 7 35 Prove that the language MULT is not regular.

Solution

Here is MULT is the binary representation of 35 which is 5 multiplied by 7 . Suppose we have two binary strings 6 and 3

then we have mult is 18 and representation will be

(0 0 0 1 1 0) for 6

(0 0 0 0 1 1 ) for 3

(0 1 0 0 1 0) for 18

Suppose the language L is regular

Then it is recognised by a DFA with say m states. Let p be a multiplied number whose binary expansion ends with m zeros and a 1, so that

... ... ... 00 000 (n is binary) ..001 (m+k zeroes) =2^m+1n+1    for some n

The Pumping lemma says that there is a non-empty substring of the m consecutive zeros which can be \"pumped\". That is, there exists s such that 0<s<m and

n in binary000000..m+ks zeros1    is MULT for all k

But the number we have written is

q=(p-1)2^ks+1

We see that q is multiplication of p-1 and 2^ks added by 1 .

so, it is multiplication followed by addition of 1

So, L is not regular .