Is it possible to build a context-free grammar for the following language?

Question

I'm trying to solve a computational problem for which I need to build pushdown automata that accepts language: $0^n1^n2^i$, where $n \leq i \leq 2n$. Is it possible?

Answer 1

Let's use the pumping lemma, and let $p$ denote the pumping number and $L$ the language in question. Define $w = 0^p1^p2^p \in L$. Let $w = uvxyz$ with $|vxy|\le p$ and $vy \ne \epsilon$. Note that because of $|vxy|\le p$, $w' := vxy$ cannot contain both $0$s and $2$s. We consider the following cases:

• $w'$ does not contain $2$s, then $vy \ne \epsilon$ has only $0$s and $1$s, therefore $uv^2xy^2z$ contains more $0$s or more $1$s than $2$s, therefore $uv^2xy^2z \not\in L$.
• $w'$ does not contain $0$s, then $vy$ has only $1$s and $2$s, if it has $1$s, then $uv^2xy^2z$ has more $1$s than $0$s, therefore $uv^2xy^2z \not\in L$, if it contains only $2$s, then $uv^0xy^0z$ has less $2$s then $1$s, therefore $uxz = uv^0xy^0z \not\in L$.

Hence, $L$ is not context free.