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?

有帮助吗?

解决方案

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.

许可以下: CC-BY-SA归因
scroll top