What is the Regular Expression for this DFA?

Question

What is the Regular Expression for this DFA?

Progress: q0 has 0* loop and q1 has 1* loop... Perhaps the answer is 0*(10∪01)1*.

Answer 1

There are algorithms for converting a DFA to a regular expression, but with a simple DFA like this one can do it in ad hoc fashion. I’ll illustrate this in some detail as a model for thinking about such problems.

The key here is what has to happen if you reach $q_1$.

Suppose that you reach $q_1$; you’ll have to get back to $q_0$, but before that you can visit $q_2$, and you can loop there for a while. In other words, if you reach $q_1$, you can make the trip $01^*0$. You can do the same thing with $q_0$ instead of $q_2$, making the trip $10^*1$. And you can mix up any number of these trips: $(01^*0\lor 10^*1)^*$ covers every possibility for starting at $q_1$ and getting back there. (You may use the notation $+$ or $\mid$ where I’ve used $\lor$.)

But we actually start at $q_0$. What are the possibilities? We can there with any number of $0$s, including none at all: $0^*$ covers that. Or we can go to $q_1$ and eventually return to $q_0$; from the results of the first paragraph we know that $1(01^*0\lor 10^*1)^*1$ covers that. And just as in the case of trips from $q_1$ to $q_1$, we now have two types of round trip at $q_0$ that can be mixed arbitrarily, and we can combine them in the same way to get

$$\big(0\lor 1(01^*0\lor 10^*1)^*1\big)^*\;.$$

This gives us the empty word, but that’s good, because we want it.