1
$\begingroup$

Of course, whenever the Pumping Lemma for Regular Languages (or CFLs) is applied to a language $L$, only a single string $w \in L$ and $|w| \ge p$ needs to be picked (to eventually show that $w$, when pumped, leaves the language).

Is there a non-regular (or non-context-free) language $L$ for which every string $w \in L$ having $|w| \ge p$ can be used to derive a contradiction?

$\endgroup$
4
$\begingroup$

I'd say the language $L = $ { $0^n1^n | n > 0$ } fits the bill for the Pumping Lemma for Regular Languages. Any substring to be pumped would consist either of all the same symbol, in which case pumping up produces a string with an unequal number of $0$'s and $1$'s, or it contains instances of both symbols, in which case pumping up produces a string with a $1$ followed by a $0$; in neither case is the pumped-up string in $L$.

$\endgroup$
  • $\begingroup$ Of course, couldn't even remember this example. Thanks! $\endgroup$ – Ryan Mar 23 '17 at 22:29
  • $\begingroup$ And of course $\{0^n 1^n 2^n\;|\;n \ge 0\}$ will work for CF. $\endgroup$ – Ryan Mar 23 '17 at 22:29
0
$\begingroup$

I'm not sure if I quite understood the question properly, but:

If a language $L$ is non-regular, then it might be context-free and in this case a contradiction can be provided as you explained for regular languages.

If a language is known to be non-CFL, then I would say there's no point of proving anymore that that language is not context-free. But if you want to do it again for any string $w$ in that language, at least the string must be able to be presented in the form $$w = uvwxy,$$ such that

  • $|vwx| \leq l$, or the middle part of the string between $u$ and $y$ isn't very long
  • $vx \neq \epsilon$, or at least another of the parts to be pumped $v$ and $x$ is not empty
  • $uv^kwx^ky ∈ L$ for every $k ∈ \mathbb{N}$, or we can pump them in balance for an arbitrary amount $k$ and still belong in the language $L$.
$\endgroup$

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.