Consider the following alphabet: sigma = {[0 0], [0 1], [1 0], [1 1]} Here, sigm
ID: 3838526 • Letter: C
Question
Consider the following alphabet: sigma = {[0 0], [0 1], [1 0], [1 1]} Here, sigma contains all rows of 0s and 1s of size 1 (one row). A string of symbols sigma is gives two columns of 0 and 1 's. Consider each column to be part of a binary number, that is, all the first columns form a binary number and all the second columns form the other binary number. Let: L = {w sigma* | the binary number formed by the last columns of w is twice the binary number formed by the first columns) For example: w = [0 0] [0 1] [1 0J [0 0) L (because the first columns form the binary number 0010 = 2 and the second columns form the binary number 0100 = 4, and 4 is twice 2)and while w = [0 0] [0 1] [1 0] [0 1] L (because the first columns form the binary number 0010 = 2 and the second columns form the binary number 0101 =5, and 5 is not twice 2). Show that L is regular.Explanation / Answer
In order to prove that Language is Regular here, we need to make use of the
Shift operation property in Regular languages.
Regular languages are closed under Shift operation.
Since the current question involves, shift operation
the Language given here is Regular.
Here, if we read the first column of the input and left shift the same by
1 bit then we should get the 2nd column. If yes, then its Regular else non-Regular.
For given example,
w = [0 0] [0 1] [1 0] [0 0],
the first column would be 0010 = 2.
Last column is 0100 = 4.
Remember, multiplying by 2 is equivalent to shift by 1 bit for Binary Numbers.