1
$\begingroup$

Consider the language $$L = \{ x \in \{0,1\}^* \mid |x| = 3 \}.$$

I think the above language is regular. A DFA can be used to determine the above language.

Am I correct? Is the above language regular?

If this language $L$ is regular, then it should satisfy the pumping lemma. Then there exist $w = xyz$, where $xy^nz \in L$ for all $n \ge 0$.

But on the other hand, if we pump more letters then the resulting string will not be in the language. The language $L$ only contains words of length 3.

The pumping lemma states that for every regular language there exists an integer $p$, such that string $w$ of length at least $p$ can be written as $w = xyz$ and $y$ can be pumped.

Here are my doubts.

  1. Is this language $L$ regular?
  2. If so, does it satisfy the pumping lemma?
  3. The pumping lemma states that every regular language has a pumping length $p \ge 1$. Does this language not have one?
$\endgroup$
2
  • $\begingroup$ I don't understand your notation. Is x a finite word over the alphabet {0,1} (meaning that it is a word consisting of these letters), or is it a one letter word which can either be the word "0" or the word "1"? What is your "/" notation? $\endgroup$ – LokiRagnarok Jun 24 '20 at 12:09
  • $\begingroup$ The language consists of all the 3 length words made over the alphabet {0,1}. E.g 000, 111, 010 etc. This is what i tried to convey. Here x is a finite word over the alphabet {0,1} which is of length 3 $\endgroup$ – PAZHAMALAI M UEE14227 Jun 24 '20 at 12:35
1
$\begingroup$

Every finite language is regular. If $L$ is a finite language and $p$ is larger than the length of all words in $L$, then $L$ satisfies the pumping lemma with the constant $p$. Indeed, every word in $L$ of length at least $p$ can be pumped (vacuously).

$\endgroup$
7
  • $\begingroup$ Thanks @Yuval Filmus for editing my question. $\endgroup$ – PAZHAMALAI M UEE14227 Jun 24 '20 at 13:00
  • $\begingroup$ I wrote that if $p$ is larger than the length of all words in $L$, then $L$ satisfies the pumping lemma with the constant $p$. I'm not sure how you concluded that $L$ doesn't have any pumping constant. What I wrote is exactly the opposite. $\endgroup$ – Yuval Filmus Jun 24 '20 at 13:02
  • $\begingroup$ I can't think of any pumping constant p for this language L. Is this language does not have any pumping constant p?. But pumping lemma states that every regular language has a constant p >= 1. $\endgroup$ – PAZHAMALAI M UEE14227 Jun 24 '20 at 13:04
  • $\begingroup$ The proof of the pumping lemma shows that you can take $p$ to be the number of states in a DFA for $L$. Your language can be accepted by a DFA having 4 states. So you can take $p = 4$. $\endgroup$ – Yuval Filmus Jun 24 '20 at 13:05
  • $\begingroup$ Ok. So we take p = 4. Now since there are no words in the language of size 4, it satisfies Pumping Lemma. Correct? $\endgroup$ – PAZHAMALAI M UEE14227 Jun 24 '20 at 13:10
0
$\begingroup$

Take pumping length = 4. All strings in the language with length greater than the pumping length must meet some condition. Since there are no strings in the language with length > 4, all these strings, all zero of them, meet any condition, and therefore the language is regular.

That’s true for any finite language where you can just take the pumping length longer than the longest string in the language.

$\endgroup$

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.