# What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)

I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as

$$(0+0001)((1111)^*+(00)^*)$$

1. What is the length of the longest string that cannot be pumped?
2. What is the length of the shortest string that can be pumped, I think this will come naturally when we find the $$p$$ (the pumping length).

The pumping length of a regular language $$L$$ is the minimal $$p$$ such that every word $$w \in L$$ of length at least $$p$$ can be split as $$w = xyz$$ such that (i) $$|xy| \leq p$$, (ii) $$y \neq \epsilon$$, (iii) $$xy^iz \in L$$ for every $$i \geq 0$$.

As per the answer https://cs.stackexchange.com/a/83727/33673, can we chose $$y$$ (the middle term in $$xy^iz$$ to be $$1111$$ in this case?

• Welcome to COMPUTER SCIENCE @SE. Please add definitions of at least not-so-standard terms and designators to your question - look how the answer you linked introduces $p$ (as you almost did $y$: there is a closing parenthesis missing right after $z$). (You can give the hyperlink a title putting it into square brackets preceding the URL in parentheses [minimal pumping length of $(01)∗$](https://cs.stackexchange.com/a/83727).) – greybeard Oct 4 '20 at 21:00

1. It will be convenient to distribute the concatenation to get the equivalent RE $$0(1111)^\ast + 0(00)^\ast + 0001(1111)^\ast + 0001(00)^\ast.$$ Now note that any such string can be writen as $$s = s_i(s_r)^\ast$$ where $$s_i$$ denotes the initial part (i.e. $$0$$ or $$0001$$) and $$s_r$$ denotes the repeated part (i.e. $$1111$$ or $$00$$). We see that $$s$$ can be pumped if and only if $$s_r$$ is non-empty and hence, the longest non-pumpable string is $$0001$$ and the answer is $$4$$. Indeed any string of length $$5$$ or more must have a repeatable part as defined above.
2. The two shortest strings in the language are $$0$$ and $$000$$. We see that $$0$$ clearly cannot be pumped (as $$\varepsilon$$ is not in the language) but $$000$$ can be pumped by repeating the last two zeroes arbitrarily often (and importantly we can also delete them to get $$0$$). Hence the answer is $$3$$.
• What do you mean by $p$? – Watercrystal Oct 4 '20 at 20:06
• I see. If you review the definition carefully (pay attention specifically to the quantifiers) together with the first part of my answer, you will find $p = 5$. – Watercrystal Oct 5 '20 at 8:16