Your adventures as a secret agent continue. Last time, the DFA told you to keep going, so you$$re still stuck behind enemy lines, trying to receive messages over the alphabet $\backslash$Sigma $=\{$a$,$ b$\}.$ Your home base has come up with a plan: to prevent enemy action from altering the message, they$$ll send each message to you twice, and they$$ll provide you with a DFA to recognise the language $\{$xx : x in $\backslash$Sigma $\},$ so you can verify the message has not been tampered with.

Unfortunately, this plan has run into a snag. You remember from your advanced training in models of computation that this language is not regular, so no DFA will be able to recognise it$.$

Your country believes it has a solution: instead of sending the second message unaltered, it will apply a function f to it$.$ The function f will be cleverly chosen to be a length$-$preserving injection f : $\backslash$Sigma $->\backslash$Sigma $.$Length$-$preserving$$ means that len$($f$($x$))=$ len$($x$)$ for all strings x$,$ i$.$e$.$ applying f to any string always produces a string of the same length. An injection is a function such that for all x$,$ y in the domain with x $=$ y$,$ we have f$($x$)=$ f$($y$),$ i$.$e$.$ different inputs map to different outputs.

Hence, researchers are trying to find a length$-$preserving injection f such that the language $\{$x f$($x$)|$x in $\backslash$Sigma $\}$ will be regular $$ here x f$($x$)$ is the concatenation of strings x and f$($x$).$ But is this possible?

For instance, the function f$($x$)=$ x is a length$-$preserving injection. We know that $\{$xx : x in $\backslash$Sigma $\}$ is not regular, so this particular f won$$t do$.$ Another example of a length$-$preserving injection is f$($x$)=$ reverse$($x$).$ In this case, $\{$x f$($x$)$ : x in $\backslash$Sigma $\}$ is the set of even$-$length palindromes, which is also not regular.

$1.$ Let f : $\backslash$Sigma $->\backslash$Sigma $$ be the function that turns every a into b and vice versa. For example, f$($abbabbaa$)=$ baabaabb. Prove that the language $\{$x f$($x$)$ : x in $\backslash$Sigma $\}$ is not regular.

$2.$ Prove that for every length$-$preserving injection f : $\backslash$Sigma $->\backslash$Sigma $,$ the language $\{$x f$($x$)$ : x in $\backslash$Sigma $\}$ is not regular.

$3.$ Prove or disprove the following claim: For every length$-$preserving function f : $\backslash$Sigma $->\backslash$Sigma $,$ the language $\{$x f$($x$)$ : x in $\backslash$Sigma $\}$ is not regular. $($Note that in the bonus part, f is not necessarily an injection.$)$ Do not use the pumping lemma.