patternModerate
Is it compulsory that every infinite set be non regular?
Viewed 0 times
infinitenonregulareverythatcompulsoryset
Problem
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,....\}$
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.
"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'sThe 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.
Solution
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.
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.
Context
StackExchange Computer Science Q#23776, answer score: 10
Revisions (0)
No revisions yet.