I know that this language is not regular L = {w | na(w) = nb(w)} where na(w) is the number of a's in w. But what if now the language changes to that the number of a's has to be greater than b's? I think not, because we do not have finite number of prefix equivalence class. And in that case, how can I prove it? Or if it was regular, how would it be?

  • 2
    $\begingroup$ Please do not delete your question after receiving an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others in the future. Deleting your question after receiving an answer can be considered impolite to answerers. $\endgroup$
    – D.W.
    May 29, 2021 at 7:24

1 Answer 1


Both mentioned languages are irregular

This can be easily shown for both languages using the pumping lemma

First consider L = {w | w has more as than bs} Let p be the pumping length then clearly b^p a^(p+1) is in L and it cannot be pumped

We know that |xy| ≤ p ,and thus x and y will have only bs , then pumping the string for i > 1 , xy^i z will give you a string with bs equal to (for i=2) or more than ( for i >2) as, since this string cannot be pumped L is irregular

In a similar manner the language with the number of as equal to bs can be shown to be non-regular , consider a^p b^p clearly it has equal number of as and bs , using the same argument as above x and y will have only as and thus pumping the string gives more as than bs and thus this language is also non-regular

Intuitively we know both are irregular since we need to keep count of the number of as and bs to compare them something , and the number of as and bs is not a finite specified number .


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.