I am studying Automata using the Coursera course created by Jeff Ullman. On slide 36 of this presentation: http://spark-public.s3.amazonaws.com/automata/slides/3_fa2.pdf it says that the language is not regular.
The language:
$$L_1 = \{0^n 1^n \mid n \ge 1 \}$$
“The set of strings consisting of $n$ $0$’s followed by $n$ $1$’s, such that $n$ is at least $1$.
Could someone explain me why?
What if I have an automata that works like this:
x means not available
State | 0 | 1
-------------
0 | 1 | x
1 | 1 | 2
2 | x | 2
This DFA accepts the language right or am I mistaking?
Your automaton accepts the regular language $00^*11^*$, i.e., $\{0^m1^n:m,n\ge 1\}$; there is nothing in it that ensures that you get the same number of zeroes and ones. For example, it accepts $011$, which is clearly not in $L_1$.
$L_1$ is in fact the classic example of a context-free language that is not regular (and therefore is not accepted by any DFA).