Prove that the Language $L= \{ 0^n1^m \;|\; n,m \ge 0 \}$ is regular

Question

I've looked and didn't find an answer. I know that languages like $\{ 0^n1^n \;|\; n \ge 0 \}$ and $\{ 0^n1^m \;|\; m \gt n \ge 0 \}$ are irregular so I don't understand how this language can be a regular language? It needs to count $n \; 0's$ and then $m \; 1's$ for any $n$ and $m$. I'd be happy if someone could explain that to me. Thanks.

Answer 1

Note that $w\in L$ if and only if $w$ starts with a sequence of zeros followed by a sequence of ones (the length of each sequence can be zero).

So to build a DFA for the language you can check:

1. If the first letter in $w$ is $1$ then all of $w$ must be ones

2. If the first letter in $w$ is $0$ then after we see the letter $1$ we must have all the letters $1$

Note that counting is not required! In your examples you needed yo know something about the amount of times each letter ($1$ or $0$) appears, but here we just care about the order