2
$\begingroup$

Is this the appropriate way to show that this language is not context-free?

Given the language $L$ containing the words $1$, $101$, $101001$, $1010010001$, where each word $L_n$ is of the form $10^110^21...10^{n-1}10^n1$.

Assume that $L$ is context-free, and as such that there is some $p$ which is the pumping length for $L$.

Consider $s = L_{p-1}$. It is trivial to show that $|s| \geq p$.

By the pumping lemma, we should be able write $s$ in the form $s = > wvxyz$ where $|vxy| \leq p$ and $|vy| \geq 1$ such that $wv^ixy^iz \in > L$ for all $i$.

As $i = 0$, being a possible number of repeats, would give $wxz \in > L$.

Therefore, as $L$ only permits deletion from the tail of words we can derive that $x = \lambda$ and $z = \lambda$.

Also we can see that either $v$ or $y$ must equal $0^{p-1}1$. We can confirm that $|vxy| \leq p$ holds for this.

However, $i = 2$ is also a possible number of repeats, but would result in a word that ends $0^{p-1}10^{p-1}1$ and therefore that is not contained in $L$.

Therefore we have a contradiction, and $L$ is not context-free.

Thankyou for your comments. Yes, this is homework.

  • 0
    See also [this question on cs.SE](http://cs.stackexchange.com/q/265/98).2012-10-26

1 Answers 1

2

You're on the right track (certainly avoiding the most common fallacies in using the pumping lemma) but the logic is incomplete. It's not quite true that $L$ only permits deletion from the tail of words. Deletion from near the tail is also possible, such as 101001000100001.

There will no doubt be more than one way to complete the argument. One simple option is to divide into two cases depending on whether $vy$ contains any 1, and make deductions about the distribution of spacings between pairs of 1s in either case.

  • 0
    Yes, using $x = \lambda$, $z = 0^i1$, with either $v$ or $y$ being $0^i10^{p-1-i}$ for some 0 \leq i < p - 1 I think I can cover all the possible deletions.2012-10-26