-3
$\begingroup$

I want to prove this language $a^nb^m; 0 \leq n< 3m+2$ to be not regular by the pumping lemma. This is my attempt, is this a correct way of doing it?

Let's suppose $L$ is regular. Let $s = a^{3k+1}b^{k}$ such that $k \geq 0$ as a pumping length. So we have $s \in L$ and $|s| \geq k$.

Then, by the pumping lemma, $\exists s = xyz$ such that

  1. $|xy| \leq k$,

  2. $|y| > 0$,

  3. $\forall i \in \mathbb{N}, xy^iz \in L$

Since $|xy| \leq k$ and $|y| > 0$, then $x = a^\alpha$, $y = a^\beta (\beta \in \mathbb{N}^*)$, $z = a^{3k+1 - \alpha - \beta}b^{k}$, so $xy^iz = a^{3k +1 + i \beta - \beta}b^{k}$

Now, $xy^iz \in L \iff 3k +1 + i \beta - \beta < 3 k + 2\iff \beta(i-1) < 1$, and so $xy^iz \notin L \iff \beta(i-1) \geq 1$, which is true for $i = 2$. Thus, as this is in contradiction with the third assumption of the pumping lemma, $L$ is not regular.

$\endgroup$
1
  • 1
    $\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$
    – Nathaniel
    Dec 21, 2022 at 13:55

1 Answer 1

0
$\begingroup$

There are two quite general classes of languages that don’t fulfil the pumping lemma: (1) a^n where n is an element of an infinite set with arbitrary large gaps between set elements. (2) a^n b^n for n >= 0.

And the generalised pumping lemma says: If L is regular then any set of substrings of elements of L fulfils the pumping lemma.

This solves practically all problems posted here very quickly. Every string a^n b^n is a substring of some string of your language, so by the generalised pumping lemma and (2) the language is not regular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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