1
$\begingroup$

If the alphabet is $\{0,1\}$, then is the string '010' regular?

I think it is regular because DFA and regular languages are equivalent and this string has a DFA but at the same time it seems to contradict pumping lemma which implies not regular. Here is what I mean.

For pumping lemma first we have to take $w$ only in the language (here the language is just '010') So $w=$ '010'. I choose $k = 2$ then the new string $w=xy^kz$ has length more than 3 so it is definitely not '010', which means this language is not regular!

What am I missing?

$\endgroup$
11
$\begingroup$

Being regular is a property of languages, not of words.

However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, $\{ 010 \}$. This language, just like any other finite language, is regular.

Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.

If $L$ is a regular language then there exists a constant $n$ such that for all words $w \in L$ of length at least $n$ there is a decomposition $w = xyz$, where $|xy| \leq n$ and $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$.

Your argument is ignoring the constant $n$, which could be larger than the length of all words in $L$.

$\endgroup$
  • $\begingroup$ Thank you. I got it. $\endgroup$ – Anirudh Feb 20 at 2:59

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.