Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
See also this question on cs.SE. –  Raphael Oct 26 '12 at 11:06
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks, excellent point there. I beleive that there is a solution by using $0^i10^{p-1-i}$. –  thomasfedb Oct 26 '12 at 5:10
    
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. –  thomasfedb Oct 26 '12 at 5:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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