2

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?

Brian M. Scott
  • 616,228
user3302735
  • 93

1 Answers1

1

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).

Brian M. Scott
  • 616,228