2
$\begingroup$

Suppose we have a regular language that describes every string with the exact length of 3.That is obviously a regular language and it still can't be pumped because there is no cyclic behavior in that string/ the corresponding dfa

Can you please help me figure out my mistake?

$\endgroup$
5
$\begingroup$

Have a look at the exact wording of the pumping lemma: It has a precondition that only words exceeding a certain size need to be pumpable. This is exactly so that only words with repetitions have to be pumpable.

For your language (and every other finite one) you can simply set that size beyond the maximum word size (e.g. at 4). No words are longer than that, and all of them can be pumped.

$\endgroup$
  • $\begingroup$ "Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can be split into three substrings," doesn't that mean that all strings have a p that so that they are pumpable? also if you set the maximum size of the language to 4 it wouldn't be the same language anymore ? $\endgroup$ – AimBlack Aug 24 '15 at 14:53
  • $\begingroup$ No, each regular language has such a constant p (not every word in it). Your language has a p = 4. This is not setting the maximum size of the language (or changing anything about the language). $\endgroup$ – Bergi Aug 24 '15 at 14:57
  • $\begingroup$ Oh yes you are right ! But if there are no words with that length then how can I pump them ? $\endgroup$ – AimBlack Aug 24 '15 at 15:05
  • $\begingroup$ If there are none, you don't need to pump any, but the requirement is still fulfilled for all of them. See also en.wikipedia.org/wiki/Universal_quantification#The_empty_set $\endgroup$ – Bergi Aug 24 '15 at 15:06
  • $\begingroup$ Oh yes and for context free languages you can't simply choose a p like that! Thx I finally got it. I really appreciate your help ! $\endgroup$ – AimBlack Aug 24 '15 at 15:14

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.