Is the language $L=\{ww^f|w\in \{0,1\}^*\}$ CFL?

Question

Where $w^f=$flipping the bits of w.

For example, $(0010)^f=1101$, $(010111)^f=101000$

I tried to prove that $L$ is not CFL using the pumping lemma, with no succeed.

In addition, I need to prove that $\overset{-}{L}$ is CFL (and to find a CFG), But it seems that both of $L$ and $\overset{-}{L}$ are the same.

Answer 1

For the first question, $0^n1^n0^n1^n0^n1^n$ is working for the pumping lemma, as Dan Shved said.

For the second question, what is $\bar L$ ? any word that does not belong to $L$. So either :

1. a word of odd length
2. a word $w.\alpha.x.\beta.z$ with any words $x,y,z$ such that $|w|+|z|=|x|$ and two identical letters $\alpha$ and $\beta$. As $\alpha=\beta$, when you cut your word in two halves, they won't be the flipped of each other.

So you can build a grammar as

• $S\rightarrow E|F$ ($E$ for even, $F$ for odd (to avoid confusion between $0$ and $O$)
• $L\rightarrow 0\;|\;1$ ($L$ is any letter)
• $F\rightarrow L\;|\;LFL$
• $E\rightarrow E_0E_0\;|\;E_1E_1$
• $E_0\rightarrow 0\;|\;LE_0L$
• $E_1\rightarrow 1\;|\;LE_1L$

As you have a grammar for $\bar L$, it is a CFL.