I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it?

say L is irregular, if we add or remove finite number of words can we create a regular language?

i might be mistaken, but since all regular languages are finite - if we add a finite amount to a non regular language - it still stays non regular, but if we substract, let's say a finite amount from infinity, it is still infinity.

so is it safe to say that in both cases a regular language cannot not be obtained by adding/substracting a finite amount of words?

i was told to ask this question here rather then in softwareengineering.

thank you very much for your help. really curious about that

  • 1
    $\begingroup$ No, since regular language is closed under intersection and union and complement and all finite languages are regular. $\endgroup$
    – John L.
    Dec 2 '18 at 15:40

We have a language $L$ which is non-regular. We subtract a finite subset $S \subset L$ of words in $L$ to get the rest: $R = L \setminus S$.

Assume that $R$ is regular. Since regular languages are closed under union, and finite sets of words are trivially regular, we can construct a language $L' = R \cup S$ which is also regular.

Since $S \subset L$, we have $(L \setminus S) \cup S = L$, thus $L' = L$. But $L'$ is regular while $L$ is not - a contradiction. Thus our assumption that $R$ is regular was wrong.

  • $\begingroup$ thank you very much. learnt so much from your answer. i was wondering, if i did the same for R=L+S where s was a finite amount of words, the proof would still be the same or do i have to consider other things that i forgot? (in case of addition rather than substraction like you showed). thank you very much $\endgroup$
    – mathnoobie
    Dec 2 '18 at 20:22
  • $\begingroup$ @mathnoobie You do have to change the argument a bit, but it's the same in spirit. $\endgroup$
    – orlp
    Dec 2 '18 at 23:03

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.