0
$\begingroup$

I'm having a little bit of an issue with a pumping lemma problem. I've successfully completely all my other problems but this is the last one and I'm a little confused I must say. If anyone can help me out, it'd be much appreciated.

\begin{equation} A = \{a^n b^m c^l \mid n\leq m \vee m\leq l\} \end{equation}

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ take $a^nb^n$ (no $c$'s) and pump up the $a$'s. $\endgroup$ – Ran G. Mar 12 '13 at 1:28
  • $\begingroup$ @RanG., that doesn't belong to the language. But $a^N b^N c^N$ does, take $N$ as the pumping lemma's constant, you can pump up the $a$. $\endgroup$ – vonbrand Mar 12 '13 at 8:23
  • 1
    $\begingroup$ @vonbrand: It does, since $n\leq n \vee n \leq 0$ is true. $\endgroup$ – frafl Mar 12 '13 at 8:35
  • $\begingroup$ @frafl, no coffee yet (misread $\wedge$ for $\vee$) $\endgroup$ – vonbrand Mar 12 '13 at 9:49
1
$\begingroup$

To expand a little on Ran G.'s comment, given a pumping length of $p$, we can take the string $s=a^{p}b^{p} \in A$, then splitting into $s=xyz$, the $y$ section (the part that can be pumped) must be all $a$s, so pumping up leaves us with a string $s'=a^{p+k}b^{p} \notin A$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ My philosophy is to only provide hints to exercises. $\endgroup$ – Yuval Filmus Mar 12 '13 at 4:04

Your Answer

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