2020-03-08
((resource:WechatIMG59.jpeg|Resource Description for WechatIMG59.jpeg))
Assume this function is not hard with respect to regular language, then there exists a DFA to represent this language.
We can let p be the pumping length.
Consider the string w = 0101.
For the pumping lemma, w = 0^p10^p1 and w = xyz where |xy| <= p, |y| > 0 and xy^iz is the language for all i >= 0.
Let x = 0^k and y = 0^j and z = 10^p1 where k + j <= p and j > 0
If we take i = 2, then w = 0^(k+j)10^p1 which makes 1 no longer the middle digit which is not in the reegular language.
Thus, this machine cannot exists
(Edited: 2020-03-08) Assume this function is not hard with respect to regular language, then there exists a DFA to represent this language.
We can let p be the pumping length.
Consider the string w = 0101.
For the pumping lemma, w = 0^p10^p1 and w = xyz where |xy| <= p, |y| > 0 and xy^iz is the language for all i >= 0.
Let x = 0^k and y = 0^j and z = 10^p1 where k + j <= p and j > 0
If we take i = 2, then w = 0^(k+j)10^p1 which makes 1 no longer the middle digit which is not in the reegular language.
Thus, this machine cannot exists
First, we assume that the language L = {w = w_o,...,w_n | w' = w_o,...,w_n z, where z is floor(n/2)} is a regular language. Then if we take a sample string, say: 0^p 1 0^p 1, we can potentially use the pumping lemma to show that this language is regular. Say we have a DFA D that accepts L and let p be a pumping length.
By the pumping lemma, this language can be divided into three substrings, x, y, z. the length of x and y must be less than or equal to p and the length of y must be greater than 0. However if one chooses p to be 0, then xz would equal 0^(p-j)10^p1, which theoretically should still be in the language. But based on this, the second 1 would not be placed in the middle of the string and thus this would not be part of the language.
First, we assume that the language L = {w = w_o,...,w_n | w' = w_o,...,w_n z, where z is floor(n/2)} is a regular language. Then if we take a sample string, say: 0^p 1 0^p 1, we can potentially use the pumping lemma to show that this language is regular. Say we have a DFA D that accepts L and let p be a pumping length.
By the pumping lemma, this language can be divided into three substrings, x, y, z. the length of x and y must be less than or equal to p and the length of y must be greater than 0. However if one chooses p to be 0, then xz would equal 0^(p-j)10^p1, which theoretically should still be in the language. But based on this, the second 1 would not be placed in the middle of the string and thus this would not be part of the language.
Assume that the language is in the language. Consider the string 0^p10^p1 which is a string in the language with a pumping length p. Therefore the string can be split into the form xy^iz where x = 0^k and y = 0^j and z = 10^p1. If i = 0, then the string will be 0^(p - j)10^p1. Because p-j and p are not equal, there is not guarantee that the two halves of 0*1 will be of the same length. If that is the case, 1 will not be the n/2 bit of the string and is not in the language.
Assume that the language is in the language. Consider the string 0^p10^p1 which is a string in the language with a pumping length p. Therefore the string can be split into the form xy^iz where x = 0^k and y = 0^j and z = 10^p1. If i = 0, then the string will be 0^(p - j)10^p1. Because p-j and p are not equal, there is not guarantee that the two halves of 0*1 will be of the same length. If that is the case, 1 will not be the n/2 bit of the string and is not in the language.
((resource:IMG_5306.jpg|Resource Description for IMG_5306.jpg))
((resource:IMG_6128.JPG|Resource Description for IMG_6128.JPG))
((resource:154_03_09_2020.jpg|Resource Description for 154_03_09_2020.jpg))
((resource:20200309_141223.jpg|Resource Description for 20200309_141223.jpg))
I was not able to finish this problem. But, I attempted it. I am uploading my attempt at solving this problem.
Due to issues with uploading images for previous in-class exercise submissions, I am going to provide a summarized version of my attempt by typing up my submission for this in-class exercise and only submitting it in text format.
Okay, so what did I do?
I struggled with the concept of what it means for a function to be hard "with respect to adversaries which are regular languages." So, I spent a significant portion of time reading the problem and reviewing the preceding lecture slides in an attempt to fully understand what the question was asking.
"[H]ard with respect to adversaries which are regular languages" for a function means there is no language A in that set of adversaries such that for every n and for any y in the set {0,1}^k(n) where k is a stretch k, y is a string in the language A if and only if there is a string x in {0,1}^n such that f(x) = y.
So, what does this mean? What is this problem asking?
If I'm understanding it correctly, this question is basically asking us to show that there are no regular languages A in the class of adversary languages A' for the function f.
And, this is all I was able to finish.
I was not able to finish this problem. But, I attempted it. I am uploading my attempt at solving this problem.
Due to issues with uploading images for previous in-class exercise submissions, I am going to provide a summarized version of my attempt by typing up my submission for this in-class exercise and only submitting it in text format.
Okay, so what did I do?
I struggled with the concept of what it means for a function to be hard "with respect to adversaries which are regular languages." So, I spent a significant portion of time reading the problem and reviewing the preceding lecture slides in an attempt to fully understand what the question was asking.
"[H]ard with respect to adversaries which are regular languages" for a function means there is no language A in that set of adversaries such that for every n and for any y in the set {0,1}^k(n) where k is a stretch k, y is a string in the language A if and only if there is a string x in {0,1}^n such that f(x) = y.
So, what does this mean? What is this problem asking?
If I'm understanding it correctly, this question is basically asking us to show that there are no regular languages A in the class of adversary languages A' for the function f.
And, this is all I was able to finish.
We will let p be the pumping lemma length.
Let the string w' = 0^p10^p1. Let x = 0^k , y = 0^j ,and z = 10^p1 where j > 0 .
By the pumping lemma, w' = xy^iz , if we let i = 2 then w' = 0^(k+2j)10^p1. As a result, 1 is no longer the middle digit and it is at the end. We can see that the machine will still accept it, but it should be rejected. As a result, this machine cannot exist and the function is hard with respect to regular languages, we have proved this by contradiction.
We will let p be the pumping lemma length.
Let the string w' = 0^p10^p1. Let x = 0^k , y = 0^j ,and z = 10^p1 where j > 0 .
By the pumping lemma, w' = xy^iz , if we let i = 2 then w' = 0^(k+2j)10^p1. As a result, 1 is no longer the middle digit and it is at the end. We can see that the machine will still accept it, but it should be rejected. As a result, this machine cannot exist and the function is hard with respect to regular languages, we have proved this by contradiction.
(c) 2024 Yioop - PHP Search Engine