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?

  • $\begingroup$ 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 $\endgroup$
    – Daniel
    Jun 27 '20 at 13:43
  • $\begingroup$ 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. $\endgroup$
    – Kba_but
    Jun 27 '20 at 17:06
  • $\begingroup$ (@Daniel pimping argument? Consider answering.) $\endgroup$
    – greybeard
    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.

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

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.