Use the pumping lemma for context-free languages to show that the following language is not context-free: $ L = \{0^i 1^j 2^i 3^k \mid k=i+j \} $

So I have started like this:

Let us assume that $ L = \{0^i 1^j 2^i 3^k \mid k=i+j \} $ is a context-free language. Then $ ∃ p∈N $ such that $∀ w∈L$, $|w|≥p$, then $∃ u,v,x,y,z∈Σ^*$ such that we can write $w=xuyvz$ which is subject to the following conditions:

$ |uyv|≤p\\ |uv|>0\\ ∀ k≥0,xu^k yv^k z∈L $

Now, let $p$ be the constant in the Pumping lemma and let $w=0^q 1^p 2^q 3^{p+q}$.

Here I have gotten stuck. I am not sure about my choice of $w$ and very unsure about what I can actually say about $w$ since I know nothing about $q$ compared to $p$ except that the number of $3$'s is $p+q$. I am even doubting that it is possible to show that $L$ is not context-free. At the moment there is always the possibility that $uyv$ is in both the $1$'s and $3$'s or the $0$'s and $2$'s (if I swap $p$ and $q$), and then I could possibly pump them just fine.

What am I missing here? Been starring myself blind trying to find it.


1 Answer 1


Use $|uyv|\le p$ to avoid the cases you mention, e.g., that $u,v$ pump both the $1$'s and the $3$'s. You can choose $p,q$ in $w$ such a way that this way of pumping is not possible. There is no problem in choosing $p=q$!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.