0
$\begingroup$

I have the language $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ I and want to prove that it is not context-free by using the Pumping lemma for context-free languages. I am new to this field and I am having some problems with the constant $n$ given by the Pumping Lemma. I do not know how to express $i$ and $j$ in terms of $n$. I have come up with a few example of expressing $i$ and $j$ as $n$ but some cases are always left out.

$\endgroup$
0
$\begingroup$

You do not need to express $i$ and $j$ in terms of $n$.

Now suppose $L$ were context-free; then there would exist an $n \geq 0$ such that for every $s \in L$ with $|s| \geq n$ there would be a partition of $s = uvwxy$ such that

  1. $|vwx| \leq n$
  2. $|vx| > 0$
  3. $uv^iwx^iy \in L$ for all $i \geq 0$

Consider the example string $s = 0^n1^n0^n1^n$. Clearly, $s \in L$, and obviously $|s| \geq n$. You must now examine all the possible partitions of $s$ and show that none of them can satisfy all three of the above conditions.

$\endgroup$

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