0
$\begingroup$

I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So does a non-regular subset have strings only length $<p$? But if they have length $<p$, can't they be trivially pumped?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Being a subset of a regular language does not have to be based on the length of the strings. It can be constructed based on other properties of the strings.

I assume that by now you already know that the language $L_1$ containing strings with equal numbers of 1 and 0 is not regular. Notice that this is a subset of the language $L_2$ that contains all binary strings, which is trivially regular. It is the property of having equal 0 and 1 that makes it impossible to have a DFA/NFA that will only accept strings from $L_1$.

So if you treat all of $L_1$ as being binary strings (as elements of $L_2$), then all of them can be pumped with respect to this property. But if you consider them as having equal number of 0 and 1, then that is the time where pumping lemma fails.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot, I didn’t think that the ability to be pumped or not depends on respect to which property of the string are we pumping by $\endgroup$
    – Axo
    Feb 27 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.