PHP Search Engine

Mar 4 In-Class Exercise .

Please post your solutions to the March 4 In-Class Exercise to this thread.

Best, Chris

Please post your solutions to the March 4 In-Class Exercise to this thread. Best, Chris

-- Mar 4 In-Class Exercise

(Edited: 2020-03-04)

((resource:IMG_0258.jpg|Resource Description for IMG_0258.jpg))

-- Mar 4 In-Class Exercise

Assume this function is not hard with respect to regular languages then there exists a DFA to represent this regular language Then let p be the pumping lemma consider the string w' = 0^p10^p1 let x = 0^k and y = 0^j and z = 10^p1 where j > 0 then by the pumping lemma w' = xy^iz if i = 2 then w' = 0^(k+2j)10^p1 now 1 is no longer the middle bit that would be appended to the end so the language would be rejected but the machine would accept therefore such a machine can not exist by contradiction and by extension the function is hard with respect to regular languages

-- Mar 4 In-Class Exercise

(Edited: 2020-03-04)

((resource:image0 (4).jpeg|Resource Description for image0 (4).jpeg))

-- Mar 4 In-Class Exercise

(Edited: 2020-03-04)

((resource:Snapchat-69878581.jpg|Resource Description for Snapchat-69878581.jpg))

-- Mar 4 In-Class Exercise

(Edited: 2020-03-04)

((resource:Screen Shot 2020-03-04 at 4.07.26 PM.png|Resource Description for Screen Shot 2020-03-04 at 4.07.26 PM.png))

-- Mar 4 In-Class Exercise

Suppose M is a DFA that recognizes L where the output of the mapping function F is in that language. A string (w) in that language is (0^p10^p1). By the pumping lemma, w = xyz, where |xy|≤p, |y|>0, and where xy^iz is in the language for all i≥0. By taking i = 0, xz = 0^(p - j)10^p1 where j > 0. xz should also be accepted in the language L, but xz is not a possible output of F which means that xz is not in L which contradicts the pumping lemma. This contradiction means that the function F is hard for the adversaries which are regular languages.

-- Mar 4 In-Class Exercise

Assume this function is not hard with respect to regular languages, then there exists a DFA M such that it represents the output language of the function.

Let p be M's pumping length.

Consider the string w = 0101, which would be an output of F.

For the pumping lemma, w' = 0^p10^p1

Let x = 0^k and y = 0^j and z = 10^p1 where j > 0

Then by the pumping lemma, w' = xy^iz

If i = 2, then w' = 0^(k+2j)10^p1 which makes 1 no longer the middle digit that would be added to the end of the string, so the language would reject it, but the machine would accept.

This is a contradiction, thus the machine cannot exist.

(Edited: 2020-03-04)

Assume this function is not hard with respect to regular languages, then there exists a DFA M such that it represents the output language of the function. Let p be M's pumping length. Consider the string w = 0101, which would be an output of F. For the pumping lemma, w' = 0^p10^p1 Let x = 0^k and y = 0^j and z = 10^p1 where j > 0 Then by the pumping lemma, w' = xy^iz If i = 2, then w' = 0^(k+2j)10^p1 which makes 1 no longer the middle digit that would be added to the end of the string, so the language would reject it, but the machine would accept. This is a contradiction, thus the machine cannot exist.

-- Mar 4 In-Class Exercise

(Edited: 2020-03-04)

((resource:20200304_173728.jpg|Resource Description for 20200304_173728.jpg))

-- Mar 4 In-Class Exercise

If M is a DFA which recoganizes language L There exists the language L = {wz | w={0,1}*, z=w[n/2]} And we can have 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,taking i=0,xz=0^k10^p1 which is not in the language of L. By contradiction, this is not accepted by the langauge of L.