1

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

say L is irregular, can we add or remove finite number of words to 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?

  • 5
    This question might be a better fit for Computer Science, but consider expressing your question more formally first. E.g. you want to “add or remove a finite number of elements” – what is an element here? A word w in the language L? And what precisely do you mean by a non-regular language? Something like context free or recursively enumerable languages (i.e. the enclosing sets of languages in the Chomsky hierarchy)? – amon Dec 2 '18 at 14:44
  • Note that looking at this problem in reverse might be simpler: can adding a finite number of words w1, w2, … wn to a regular language L make that language non-regular? No, the resulting language is still regular. The language could e.g. be described with the regular expression w1|w2|...|wn|R where R is a regular expression describing the original language L. The question whether removing a number of words from a regular language keeps the language regular is more difficult, but I think it could be proven by using an NFA. – amon Dec 2 '18 at 14:49
  • thank you very much for your comment - i am in the beginning of the course and we have not yet encountered chomsky hierarchy. by element i meant words, and i will correct that in an edit – mathnoobie Dec 2 '18 at 14:50
  • i didn't understand the second comment quite well. the question is about adding/substracting a finite amount of words from a non regular language, i.e if we add/substract a finite amount of words from a nonr regular language - can make it regular? and i think that the answer is no – mathnoobie Dec 2 '18 at 14:54
  • 2
    thank you for your comment akiva, but this is the term that is regularily being used in automata theory: regular and non regular languages. even why i searched in google and similar sites before asking the question, all were using the same terminology – mathnoobie Dec 2 '18 at 15:30
6

Finite Languages are trivially enumerable just by listing their members, and thus weaker than even the regular languages. Therefore the entire hierarchy of formal languages deals only with infinite languages, and every higher-up language is infinite in a qualitatively new way. For instance, regular languages can't count things, but context-free languages can.

None of these differences can be bridged by adding a finite number of elements, so yes, neither adding nor removing them can move between regular and non-regular.

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.