0

I was shown a way to prove this language was not context free by intersecting it with a regular language, however I can't find a string to pump to show that this language is false directly through the pumping lemma.

My original thought was just to use the string $(a^n)(b^n)(c^n)$, but it's possible to pump this string just $w=uvxyz$ by picking $v=ab$ and $y=c$.

Another idea was to use string $(abc)^n$, but the same issue persists.

What is a suitable string to pump a language as loosely defined as this? Is it not always possible to pick a $v$ and $y$ that just consists of some combination of $ab$ and $c$, $a$ and $bc$, etc? I feel like I'm missing something very basic.

EDIT: After checking my book it seems like it's implied that this is one of those CFG's that, even though it passes the pumping lemma, we can't know for sure if it's context free or not (and this case we know it's not). So the intersection with regular set is one of the alternatives to the pumping lemma.

pajkatt
  • 373
  • Out of interest, what is a nice regular language to intersect it with to see that $L$ is not context-free? – Joppy May 07 '17 at 11:20
  • 1
    @Joppy $abc*$, intersecting with L gives $a^nb^nc^n$, which we can show to be not context free. Because the intersection of a regular set with a context free grammar is a closure property, L cannot be a context free because if it were, then it's intersection with the regular set would be context free. – pajkatt May 07 '17 at 19:36

1 Answers1

0

Your original thought is correct. You can use the string $a^nb^nc^n$ to prove that the language $M\equiv L\cap a^*b^*c^*$ is not context-free. Then because $M$ is not context-free, $L$ is not context-free either.

If $M$ is context-free, then by the pumping lemma, all sufficiently long strings are pumpable. Suppose $p$ is the pumping length, so that all strings longer than $p$ are sufficiently long, and consider the string $a^pb^pc^p \in M$.

By the pumping lemma, we should be able to subdivide $M$ into the form $M=\mathsf{uvwxy}$ such that (1) $\mathsf{uv}^k\mathsf{wx}^k\mathsf{y}$ is in the language for every $k\geq 0$, (2) the pumped components $\mathsf{v}$ and $\mathsf{x}$ aren't both empty, (3) the middle part of the string, $\mathsf{vxy}$, is shorter than $p$, the pumping length.

This third condition is what breaks it. In order for the pumped string to be in $M$, we know that $\mathsf{vx}$ must have the same number of $a$'s $b$'s and $c$'s. One option is for $\mathsf{vx}$ to be empty—but that option is excluded by (2). Hence $\mathsf{vx}$ must have at least one $a$, $b$, and $c$. But our string $a^pb^pc^p$ is so long that we can't possibly capture an $a$, $b$ and $c$ without causing $\mathsf{vwx}$ to be longer than $p$ (it has to span the entire length of $b^p$ in the middle!).

Hence there is no way to subdivide $a^pb^pc^p$ to make it pumpable. Hence $M$ isn't context-free, so $L$ isn't either.

user326210
  • 17,287