Consider the following alphabet: sigma = {[0, 0], [0 1], [1 0], [1 1]} Here, sig
ID: 3838149 • Letter: C
Question
Consider the following alphabet: sigma = {[0, 0], [0 1], [1 0], [1 1]} Here, sigma contains all rows of 0s and 1 s of size 1 (one row) A string of symbols in sigma 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 and 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 0] [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
This, is very simple but with a catch we just need to understand the logic behind it,
Consider the entire as a single string, then we can easily solve the question,
There are a few important points we need to understand before solving the question:
1) A language is regular if we have a grammar/regular expression for it.
2) If a number is twice of any other number it's always even and hence ends with a '0' => last digit of our entire string is always zero.
3) In binary format, multiplication by 2 is just that we need to shift the position by one digit => If the first digit is 1 it has no place to be shifted and should always be zero.
4) Since, the other digits are just formed by shifitng the previous didgits, the digits in the n-1th place and n-2nd place must be same, similarly, the digits in n-3rd and n-4th and so on.
From, using all the above facts we can see that,
L = 0(xx)*0; x = 0/1
We, can see that the given example in the question satisfies it
=> 0 0 0 1 1 0 0 0 ------------------- > 0 (00) (11) (00) 0
and also
=> 0 0 0 1 1 0 0 1-------------------------> last digit is 1, hence not part of L
Therefore, we can say that L is regular and the required regular expression is L = 0(xx)*0; x = 0/1