0
$\begingroup$

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;

A^aA^ibA^p-a-bA^p

= 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.

Thanks.

$\endgroup$
2
  • $\begingroup$ You seem to read your regular expression as $(a+b)(a^*+b^*)$ but that's not what you wrote. $\endgroup$
    – Kai
    Feb 21 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$ Feb 23 at 16:58

0

Your Answer

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

Browse other questions tagged or ask your own question.