# Is this language with prefix regular?

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?

• Yes, the language is not regular. However, you didn't consider every possibility of decomposing z into u, v, w as v can contain both a's and b's. And your argumentation at the beginning is not completely correct. I'm pretty sure you mean intersection and not concatenation of two languages. Moreover I don't think this step is necessary as the pimping argument works for the original language as well Jun 27 '20 at 13:43
• Thank you. Is it possible that there are two version of pumping lemma for regular language? I see that here on this forum is pumping lemma where we consider 3 cases of decomposing. Something like pumping for cfg. But my teacher show version when we consider only pumping on beginning of string. I'm confused now. Jun 27 '20 at 17:06
• (@Daniel pimping argument? Consider answering.) Jun 28 '20 at 8:08

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.

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