I'm trying to figure out the pumping length of (a+b)(a+b)*

From what I understand, this means that there is some A or B followed by any number of either A's or B's e.g

ABBBB or AAAAA but AAAABA wouldnt be in the language.

Firstly I'm not sure if my assumption above is correct.

Using the decomposition rule.

Suppose L is regular.

Choose w = AA^p

Look at all decomps of w.

xyz =

x = A^a y = A^b z = A^p-a-b A^p

Now we look at xy^iz; where i is the pumping length;


= p+ib-b < p

= b(i-1) < 0

So the lowest I can be is 2 because we know b is at least 1.?

Which doesnt make sense.

Can someone point me along the right lines please.


  • $\begingroup$ You seem to read your regular expression as $(a+b)(a^*+b^*)$ but that's not what you wrote. $\endgroup$
    – Kai
    Commented Feb 21, 2023 at 0:58
  • $\begingroup$ Not only that, but the notion $A^a$ needs to be explained. It's at best non standard, or more likely is incorrect. $\endgroup$ Commented Feb 23, 2023 at 16:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.