Is it compulsory that every infinite set be non regular?

Question

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.

Answer 1

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.

Answer 2

You must have misunderstood the comment, since the set $\Sigma^*$ is infinite and regular. The correct notion of "infinite" is given by the Myhill–Nerode theorem. Every language is associated with a set of states, and a language is regular iff the set of states is finite.

A state in a language $L$ is a set of strings $S$ that are interchangeable with respect to $L$ in the sense that for all words $x$, either all words of the form $sx$ (where $s \in S$) are in $L$, or all are not in $L$. In the example $L = \{0^n 1^n : n \geq 0\}$, the states are $\{ 0^{m+n} 1^n : n \geq 0 \}$ for each $m \geq 0$, all other words forming another state. You can see that there are infinitely many states, and so the language is not regular.

Every regular language has a DFA whose states correspond to the states described above. This DFA is known as the minimal DFA. A "minimal DFA" for $\{ 0^n 1^n : n \geq 0 \}$ would need to have infinitely many states, since the DFA would have to remember how many zeroes it has seen so far, or more generally how many ones it expects at this point (if the next symbol is a one). No finite automaton can remember that much information, so the language isn't regular.

Answer 3

"Is it compulsory that every infinite set is non regular though every finite set is a regular set".

No.

All finite sets are regular but infinite sets may or may not be a regular set. An infinite as well as regular set example is $a^*$ And an infinite but non-regular example is $\{ a^nb^n$ | $n > 0 \}$.

See the Venn-diagram below: In Venn-Diagram every finite set is regular. Infinite set may be regular or not. Actually, class of regular-languages ⊆ set of all possible infinite sets.

Venn: Show class of regular sets are subset of set of all infinite stes

Some interesting points to be notice that will help you to understand properties of regular language e.g. pumping lemma:

• Any finite automata (without dead state) for a finite language does not contain a loop. Also regular expressions for finite language will be without $*$ "star clouser" and $+$ "plus clouser" operation.
  (read Raphael♦'s comments: a complete DFA defined on δ: Q×Σ → Q may contains loop but I am talking about partial δ ⊆ Q×Σ → Q that "FA without a loop that is reachable from the starting state and from which a final state can be reached").

• Any finite automata for a infinite language(regular) will contain the loop. We can't construct an automata for infinite language without loop; where loop may be a self loop of via some other state. {If its self loop then a single symbol repeats any number of time, if via other state a sequence of symbols comes in loop can be repeat any numbers of time}.

Additionally, to learn "What is called regular language?" And Why a languages like $(a + b)^*$ is regular? But language $\{ a^nb^n$ | $n > 0 \}$ is not a regular language? read this answer: I need clarification about DFA's and DFA acceptable languages.