Prove $\{0^k10^k10^k1 \in \{0,1\}^* \mid k \geq 0 \}$ is not context free

Question

I'm practising for my CS exam and got stuck on this problem

$$ \{0^k10^k10^k1 \in \{0,1\}^*\mid k ≥ 0\}. $$

I think I have good start however I don't know how to proceed. I assume the L is context free, and that pumping lemma applies with some pumping length $n$.

$$|w| = 3k,\quad w = uvxyz$$

Since $|vxy| \geq n$ it can't contain all characters. Considering $uv^2xy^2z$ would end up having more than $3$ zeros if anything is pumped in. However I'm not sure how t o move from here. Is that enough of a proof?

Answer 1

Proof that $L$ is not regular

Assume that $L$ is regular, then there exists $p$ such that for all $|w|\geq p\:, \exists x,y,z, \: y\neq \varepsilon \text{ and } \forall k, \: xy^kz \in L$.

Take $n>p$ (we're not going to be subtle here. Then $w=0^n10^n10^n1 \in L$, so we can slice it into three part $x,y,z$. Let us consider $y$

• if $1 \in y$ then $xy^kz \not\in L$, for it would contains to many $1$'s

• otherwise, $y=0^d$ for some $d$, but then $xy^kz = 0^{n_1} 1 0^{n_2} 1 0^{n_3} 1 \not\in L$ because the $n_i$ won't be equal anymore.

Hence we cannot apply the pumping lemma for regular languages, $L$ is therefore not regular.

---

Proof that $L$ is not context-free

as suggested by @posilon, we can also prove that the language is not context free by applying this pumping lemma

There exists a $p$ such that, if $|w|\geq p$ then we can slice $w = uvwxy$ such that:

• 1. $|vx| \geq 1$
• 2. $|vwx| \leq p$
• 3. $uv^n wx^n y \in L$ for all $n \geq 0$.

here again, let us consider the number of $1$'s in $vx$

• if $1 \in vx$ then $uv^n wx^n y \not\in L$, for it would contains to many $1$'s

• otherwise, $v=0^d, x=0^{d'}$ for some $d,d'$, but then $uv^n wx^n y = 0^{n_1} 1 0^{n_2} 1 0^{n_3} 1 \not\in L$ because the $n_i$ won't be equal anymore.

Hence we cannot apply the pumping lemma for context-free languages, $L$ is therefore not context-free.