patternMinor
Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?
Viewed 0 times
whygeqregularlanguagenot
Problem
I'm looking for intuition about when a language is regular and when it is not. For example, consider:
$$ L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$
which is not a regular language. Intuitively it seems a very simple language, there doesn't seem to be anything complicated going on. What is the difference between $L$ and a regular language like:
$$L' = \{ w \mid w \text{ does not contain } 11 \} = \{0,10\}^*\cdot (1 \mid \varepsilon).$$
I know how to prove that $L$ is not regular, using the Pumping Lemma. Here I am looking for intuition about what makes a language regular.
$$ L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$
which is not a regular language. Intuitively it seems a very simple language, there doesn't seem to be anything complicated going on. What is the difference between $L$ and a regular language like:
$$L' = \{ w \mid w \text{ does not contain } 11 \} = \{0,10\}^*\cdot (1 \mid \varepsilon).$$
I know how to prove that $L$ is not regular, using the Pumping Lemma. Here I am looking for intuition about what makes a language regular.
Solution
To expand on Artem's comment, note that if we have an $m$ state automaton, at each point we can remember at most $\lg m$ bits of information about the part of input we have read so far. Based on this finite amount of information about the the previous bits of the input, you should be able to end up in the right accepting/rejecting state for all possible ways that the input can continue. If this amount of information is not sufficient to answer correctly then the language is not regular.
For this language we may need $m$ bits of information to be able to correctly answer where $m$ is an arbitrary large number (and therefore can be taken to be larger than $n$ which is fixed since the same atuomaton should work for all inputs).
One way to formally show this is pumping lemma. A more general way that is harder to use is to directly show that the number of equivalence classes of strings w.r.t. the language is not finite (we say strings $x$ and $y$ belong to the same class and write $x\sim y$ if for all strings $w$, $xw \in L$ iff $yw \in L$) which is the same as saying the amount of information that the machine needs to remember is not finite (constant w.r.t. to inputs).
For this language we may need $m$ bits of information to be able to correctly answer where $m$ is an arbitrary large number (and therefore can be taken to be larger than $n$ which is fixed since the same atuomaton should work for all inputs).
One way to formally show this is pumping lemma. A more general way that is harder to use is to directly show that the number of equivalence classes of strings w.r.t. the language is not finite (we say strings $x$ and $y$ belong to the same class and write $x\sim y$ if for all strings $w$, $xw \in L$ iff $yw \in L$) which is the same as saying the amount of information that the machine needs to remember is not finite (constant w.r.t. to inputs).
Context
StackExchange Computer Science Q#1830, answer score: 6
Revisions (0)
No revisions yet.