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

  • $\begingroup$ No, since regular language is closed under intersection and union and complement and all finite languages are regular. $\endgroup$ – Apass.Jack 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

