Is $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ a context free language?

Question

I need to find and to prove (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ is a context free language.

I would like to get some help. thanks!

Answer 1

HINT: You can use the pumping lemma to show that $L$ is not context-free. Suppose that it is, and let $p$ be the pumping length. Let $s=0^p1^p01^p$; clearly $s\in L$, so $s$ can be decomposed as $s=uvwxy$ in such a way that $|vwx|\le p$, $|vx|\ge 1$, and $uv^kwx^ky\in L$ for each $k\ge 0$.

• Show that the substring $vwx$ of $s$ must be a substring of one of the substrings $0^p1^p$ and $1^p01^p$.
• Show that in each of the possible locations for $vwx$, $uv^kwx^ky$ is not in $L$ if $k=0$. Conclude that $L$ cannot be context-free after all.