I need to show the following language is not context free via the Pumping Lemma.
$$L = \{0^n\#0^{2n}\#0^{3n}\mid n \ge 0 \}$$
I was wondering if someone can help explain how to begin such a proof. I have been staring at this problem for a long time now, and I am having a hard time with this.
I appreciate any suggestions.
Many thanks in advance!
HINT: If $p$ is the pumping length, start with the word $w=0^p\#0^{2p}\#0^{3p}$. The pumping lemma says that it has a decomposition $w=uvxyz$ such that $|vxy|\le p$, $|vy|\ge 1$, and $uv^kxy^kz\in L$ for every integer $k\ge 0$. Since $1\le|vxy|\le p$, the substring $vxy$ must have one of the following forms:
$$\begin{cases} 0^m&\text{for positive some }m\le p\\ 0^m\#0^n&\text{for some }m,n\ge 0\;. \end{cases}$$
If $vxy=0^m$, you should have no trouble showing that pumping $w$ will give you a word that is not in $L$. If $vxy=0^m\#0^n$, you’ll have to look more closely at $v$ and $y$. If the $\#$ is in $v$ or $y$, it is again very easy to see that pumping $w$ takes you outside of $L$.
The hardest case is the one in which the $\#$ is in the $x$ part of the string, $v=0^k$ for some $k\ge 0$, $y=0^\ell$ for some $\ell\ge 0$, and $k+\ell\ge 1$. Then either $v$ is part of $0^p$ and $y$ is part of $0^{2p}$, or $v$ is part of $0^{2p}$ and $y$ is part of $0^{3p}$. In either case pumping will take you out of $L$; why?