1
$\begingroup$

I'm currently trying to prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma

My proof:

If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it can be pumped any number of times $i$, such that $a^{iP} b^P \in L$. Since $iP \leq P$ is not true for any $i > 1$, it cannot exist in $L$, therefore $L$ cannot be regular.

Is this a valid proof? I don't fully comprehend the pumping lemma, so please let me know if/where I may be going wrong.

Thank you

$\endgroup$
2
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Apr 11 at 2:32
  • $\begingroup$ Crosspost with this question on math.stackexchange. $\endgroup$
    – J.-E. Pin
    Apr 12 at 5:59

1 Answer 1

1
$\begingroup$

There is a bit of a confusion on the notations:

  • what is $P$? If it is the pumping length, then say it so;
  • what is $p$? Is it a typo and should be a $P$?
  • what are $x$ and $y$? Don't hesitate to remind the hypotheses of the pumping lemma;
  • why would $y$ be $a^P$? The only conclusion you can make is that $y = a^k$ for $1\leqslant k \leqslant P$.

The ideas of the proof are good but you should improve the details.

$\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.