How to show that the language containing the words which number of $b$ divides the number of $a$ isn't regular using pumping lemma?

Question

How to show that the language containing the words which number of $b$ divides the number of $a$ isn't regular using pumping lemma ?

The pumping lemma says that

Let be $M$ a regular language. Then there exists a number $p>0$ such that for each word $w\in L$, such that $|w|\ge p$, there exist $x,y,z$ such that :

1. $w=xyz$
2. $|y|>0$
3. $|xy|\le p$
4. For each $i\ge 0$ we have $xy^iz\in L$.

(I don't perfectly understand this lemma...). I have great difficulties to understand the examples [which I can provide you in French here][1].

My attempt

Let's take $w=a^{qn}b^n\Rightarrow w\in L$

• Let's assume $L$ is regular.
• I thought about taking $|w|>n$
• $x = aaaa....$ , $y = aaaa...$, $|x|=s$, $|y|=k$. We need to consider ALL the options, that is all the possible $s,k$ such that $s≥0$,$k≥1$ and $s+k≤n$.

Let's take $i=0$, then $xy^iz=xz=a^{qn-k}b^n\not\in L$ whatever may $s,k$ be and since $k\ge 1$, $L$ isn't regular at all (but why) nd we reach a contradiction.

I have some difficulties to understand the conclusion.

Answer 1

As @Hagen von Eitzen said in the comments, using $w=b^pa^p$ is a better idea. Here's a more detailed explanation.

Assume $L$ is regular. Then it satisfies the Pumping Lemma, so there exists such a number $p$ that for any word $w\in L$, $|w|\ge p$, the conditions of the lemma will be satisfied. Since it is true for any such $w$, it is true in particular for $w=b^pa^p$ — which belongs to $L$ and whose length is $2p\ge p$. By the Pumping Lemma, $w$ can be written in the form $w=xyz$, where:

• $|y|\ge1$,
• $|xy|\le p$,
• and $xy^iz\in L$ for any $i\ge0$.

Note that the condition $|xy|\le p$ implies that the $xy$ part lies entirely within the initial $p$ letters $b$ of the word $w$, so in particular $y$ consists of $b$'s only: $y=b^k$ for some $k\ge1$. Then according to the Pumping Lemma, $$xy^2z=b^{p+k}a^p\in L.$$ But that can't be true, because this word has more $b$'s than $a$'s, so the number of $b$'s does not divide the number of $a$'s.