문제

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 ~와 함께 속성
제휴하지 않습니다 softwareengineering.stackexchange
scroll top