Is this language with prefix regular?

Question

Is this language regular? ${w ∈ (a + b)∗ : |u_{a}|>= 2009 · |u_{b}|}$ for every non empty prefix $u$ of string $w$} I think it's non-regular. I tried concatenation of $L_{prefix} $={${ u : |u_{a}|> 2009 · |u_{b}|}$} and $L_{2}= a^*b^*$. $L_{2}$ is regular. I tried to show that $L_{prefix}$ is non-regular using pumping lemma. for string z= $a^{2009n} b^n$ pumping 'a' for i=0 : $$ z=uv^iw $$ $$z= uv^0w $$ $$z=a^{2009n-p} b^n$$ so there is less 'a' than 2009'b'

pumping 'b' for i=2 $$z=uv^2w $$ $$z=a^{2009n} b^{n+p} $$ again to much 'b' and less 'a' than should be. So this is non-regular language and concatenation of this two also is non-regular . Is it correct? Or maybe it's somehow regular?

Answer 1

Let $k=2009$ and $L = \{w : |u_a| \ge k\cdot |u_b|$}. I think it is easier to prove using Myhill-Neorde's Theorem.

Consider the strings $a^k, a^{2k}, a^{3k} \ldots$, we claim that all of these have a $L$-distinguishable suffix. Consider $a^{lk}$ and $a^{mk}$ with $l < m$. Let $x = b^m$. We have $a^{lk}b^m \notin L$ but $a^{mk}b^m \in L$ (Why?). Therefore, there are infinitely many $L$-equivalence classes, which proves that, by Myhill-Nerode's theorem, that $L$ is non-regular.

---

Your argument is almost correct:

Assume, for the sake of contradiction, that $L$ is regular. Therefore, by closure property of regular languages, $L' = L(a^*b^*) \cap L$ will also be regular. Notice that all the words in $L'$ will be of the form $a^{n_1}b^{n_2}$ s.t. $n_1 \ge kn_2$.
Now, consider a word $w = a^{kn}b^{n}$ in $L'$. Using pumping lemma, for a sufficiently large $n$, there should exist a partition of this string $w = xvy$ such that $v \ne \epsilon$. Now, three case arises:

1. If $v$ lies in the part $a^{kn}$: pumping down will lead to a contradiction
2. If $v$ overlaps both the $a$'s and $b$'s parts: $v$ should be of the form $a^{m_1}b^{m_2}$. Pumping up will result in a string of the form $a^{kn}b^{m_2}a^{m_2}b^{m_2 + n}$, which doesn't belong to $L'$ (why?)
3. If $v$ lies in the part $b^n$: pumping up will lead to a contradiction