I need to find whether this language is context-free or not:

{u#v | u,v belong to {a,b,c}* and u is a substring of v}, over alphabet {a,b,c,#}

I suspect that it's not, and am trying to approach it via Pumping Lemma, but then I noticed that: any examples like a^n#a^n will not work, cos we can always make vwx in the second a^n such that after pumping, u is still a substring of v; then I tried playing around with # like a#ab^(n-3), but get lost with the choice of v and x since it's possible for one of them to be empty string.

This is homework so just a hint will be okay for me.

  • 1
    $\begingroup$ See our reference question for other methods. Hint: try intersecting the language at hand with regular languages towards a non-context-free language that's easier to deal with. Use closure properties to finish the argument. $\endgroup$ – Raphael Oct 9 '16 at 12:49
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Oct 9 '16 at 12:49
  • $\begingroup$ Really sorry I really didn't expect this to cause confusion; I'm new to this community so didn't get used to maths expressions, and what I mean is u, v belong to {a, b, c}*. I'll update it again when I know how to use maths expressions. $\endgroup$ – richards Oct 11 '16 at 13:27

Okay I got confused when developing my ideas, and a simple example using Pumping Lemma would be: $a^nb^n\#a^nb^n$. Consider this: clearly $v$ and $x$ cannot contain $\#$, otherwise when pumping more or less $\#$ appear and the new string is not in the language. Now suppose $vwx$ are in the left $a^nb^n$, then $v^2$ and $x^2$ will make it longer than the R.H.S.; then if $vwx$ are in the right $a^nb^n$, then $v^0x^0$ will make the R.H.S. shorter than the left. This gives us the only possibility that $v$ in the first $b^n$ and $x$ in the second $a^n$, and clearly no matter how you pump it the new string cannot be in the same language, and this solves the problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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