-- 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.