2020-03-04
((resource:FullSizeRender.jpeg|Resource Description for FullSizeRender.jpeg))
((resource:0304.jpg|Resource Description for 0304.jpg))
Assume this function is not hard with respect to regular languages.
There exists a DFA to represent this regular language.Let p be the pumping lemma length. Let the string w' = 0^p10^p1 Let x = 0^k and y = 0^j and z = 10^p1 where j > 0 => w' = xy^iz Let’s take i = 2 then w' = 0^(k+2j)10^p1 Notice that 1 is no longer the middle digit which supposed to be put at the end However, the machine will still accept it but the language should be rejected Then, this machine can not exist and the function is is hard with respect to adversaries which are regular languages by contradiction
Assume this function is not hard with respect to regular languages.
There exists a DFA to represent this regular language.
Let p be the pumping lemma length.
Let the string w' = 0^p10^p1
Let x = 0^k and y = 0^j and z = 10^p1 where j > 0 => w' = xy^iz
Let’s take i = 2 then w' = 0^(k+2j)10^p1
Notice that 1 is no longer the middle digit which supposed to be put at the end
However, the machine will still accept it but the language should be rejected
Then, this machine can not exist and the function is is hard with respect to adversaries which are regular languages by contradiction
((resource:IMG_1460.JPG|Resource Description for IMG_1460.JPG))
2020-03-06
((resource:image0.jpg|Resource Description for image0.jpg))
2020-03-08
((resource:inclass_exercise_03-04-2020.jpg|Resource Description for inclass_exercise_03-04-2020.jpg))
((resource:image0.jpg|Resource Description for image0.jpg))
((resource:88310965_2932367360157346_7716681188542251008_n.jpg|Resource Description for 88310965_2932367360157346_7716681188542251008_n.jpg))
Let p be the pumping lemma length. Let the string w' = 0^p10^p1 Let x = 0^k and y = 0^j and z = 10^p1 where j > 0 => w' = xy^iz Let’s take i = 2 then w' = 0^(k+2j)10^p1. Notice that 1 is no longer the middle digit which is supposed to be at the end. However, the machine will still accept it. But the language should be rejected. So, this machine can not exist and the function is hard with respect to adversaries which are regular languages by contradiction.
Let p be the pumping lemma length. Let the string w' = 0^p10^p1 Let x = 0^k and y = 0^j and z = 10^p1 where j > 0 => w' = xy^iz Let’s take i = 2 then w' = 0^(k+2j)10^p1. Notice that 1 is no longer the middle digit which is supposed to be at the end. However, the machine will still accept it. But the language should be rejected. So, this machine can not exist and the function is hard with respect to adversaries which are regular languages by contradiction.
Assume this function is not hard with respect to a regular language than there exists a DFA to represent this regular language let p be a pumping lemma consider the string w = 0^p10^p1 By pumping lemma, w=xyz, x=0^k, y=0^j, where k+j<=p, j>0 and z=10^p1. Then we can get w'=xy^iz, using i=0,xz=1^k0^p1 which proves by contradiction that is not an accepted language by L
Assume this function is not hard with respect to a regular language than there exists a DFA to represent this regular language let p be a pumping lemma consider the string w = 0^p10^p1 By pumping lemma, w=xyz, x=0^k, y=0^j, where k+j<=p, j>0 and z=10^p1. Then we can get w'=xy^iz, using i=0,xz=1^k0^p1 which proves by contradiction that is not an accepted language by L
(c) 2024 Yioop - PHP Search Engine