[Solved]: Is it compulsory that every infinite set be non regular?

Problem Detail: 

I am confused regarding the statements provided by one of our faculty regarding "Is it compulsory that every infinite set is non regular though every finite set is a regular set". Providing this example:

$$L= \{ 0^n 1^n | n>=0 \} $$ its formal as $\Sigma=\{0,1\}$ and thus we've a formal meaning as $\{\epsilon,01,0011,000111,....\}$

                               no. of 0's = no. of 1's  

The above language should be a non-regular as we need to keep track the value of 'n' in order to make it a equal no, of 0's & 1's and FA has no memory.

or am i mistaken.

Please, provide some oxygen regarding this confusion.thank you.

Asked By : Terminal

Answered By : jmite

The statement should read " it is NOT compulsory that every infinite set is non-regular, though every finite set is regular." So being infinite is necessary but not sufficient for being irregular.

For example, for any alphabet $\Sigma$, the language $\Sigma^*$ is infinite but regular. In fact, a regular language will be infinite iff a regular expression generating the language contains a $*$ on some non-empty non-empty-string expresion, assuming union and concatenation are the only other operators.

A more accurate statement is that any language which needs an infinite amount of memory to recognize is non regular. For example, $\{0^n 1^n | n \geq 0\}$ is non-regular because we need to "count" how many 0s there are and see if the number of 1s matches, but since there can be any number of 0s, there is no limit to the size of the count we'd have to store. Thus, we need some unbounded memory structure, like a stack or a tape.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23776