1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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).) $\endgroup$ – greybeard Oct 4 '20 at 21:00
3
$\begingroup$
  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$.
$\endgroup$
4
  • $\begingroup$ Thanks for the answer, so the smallest 'p' that can be used in the pumping lemma is 1? $\endgroup$ – A. K. Oct 4 '20 at 19:57
  • $\begingroup$ What do you mean by $p$? $\endgroup$ – Watercrystal Oct 4 '20 at 20:06
  • $\begingroup$ p = the pumping length. $\endgroup$ – A. K. Oct 5 '20 at 4:11
  • $\begingroup$ 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$. $\endgroup$ – Watercrystal Oct 5 '20 at 8:16

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.