I try to prove that the language $L$ is not regular: $$ L = \{w\in(a+b)^*:\#_a(u)>2009\#_b(u)\ \text{for every nonempty prefix u of word w} \} $$ Note: $\#_a(u)$ means the number of symbols $a$ in the word $u$.

Let $p$ let be the length in pumping lemma. Let $w=(a^{2009p}ab^{p})^*\in L$ enter image description here

Let according to lemma $w=xyz$, where $|y|>0, |xy|\le p$. And now, look at $s'=xy^0z$. Since $y=aa...aa$ and $ 1\le|y|\le p$, the word $s'$ has no more than $2009p$ symbols $a$ in some prefix. Therefore $s'\notin L$ - so the language is not regular (thanks to the pumping lemma). What about this solution ?

  • $\begingroup$ Why did you use 2009? $\endgroup$
    – J.-E. Pin
    Mar 16, 2015 at 14:08
  • $\begingroup$ Look again on my post (I edited) $\endgroup$
    – user220688
    Mar 16, 2015 at 14:12
  • $\begingroup$ Nobody Can help ? $\endgroup$
    – user220688
    Mar 16, 2015 at 21:07
  • $\begingroup$ The argument is correct. $\endgroup$ Mar 17, 2015 at 6:24

1 Answer 1


Community answer to remove from unanswered

The argument is correct

  • 1
    $\begingroup$ @BjörnFriedrich Hi, I know this answer is not what stackexchange is for. But there are no way for me to not see again and again the same question in the unanswered questions except to answer the. (there are plenty of discussion in Meta about this situation but nothing that solve the problem). what do you sugest? (you voted to delete an other similar answer). $\endgroup$
    – wece
    Oct 8, 2018 at 14:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .