TITLE: Write the regular expression of the language that the DFA accepts.
QUESTION [1 upvotes]: I am given a DFA and I have tried to write the regular expression of the language that it accepts.
This is the DFA that I am given:

I have found some words that the DFA accepts: 000,111,01001,101110.
I noticed that it accepts an odd numbers of 0s,an odd number of 1s, and any word of the form 01/ 01/ 101 and so on.
So I thought that the expression should be of the form $((0 \{ (00)^{\star},1^+\})^{\star} (1 \{ (11)^{\star},0^+\})^{\star})^+$.
Am I right?

REPLY [2 votes]: Let me show you a systematic approach. Think of each of the state names as an abbreviation for a regular expression corresponding to the set of words that end at that state when starting from the initial state. Since $B$ and $C$ are the acceptor states, we want the expression $B+C$. (I’ll use $+$ instead of a comma for or; I use $\lambda$ for the empty word.)
The first step is to write down equations showing how we reach each of $A,B$, and $C$ in at most one step. Since $A$ is the initial state, we reach it on an input of $\lambda$. We also reach it if we’re in state $B$ and get an input of $0$, or if we’re in state $C$ and get an input of $1$. These are the only ways to reach it in at most one step, so $A=\lambda+B0+C1$: to get from $A$ to $A$, we can read the empty word, we can read any word that gets us to $B$ and then a $0$, or we can read any word that gets us to $C$ and then a $1$. If you perform the same analysis for states $B$ and $C$, you get the following system of equations:
$$\begin{align*}
A&=\lambda+B0+C1\\
B&=A0+C0\\
C&=A1+B1\;.
\end{align*}$$
Since I’m really interested in $B+C$, I’d like to eliminate $A$; I can do that by substituting the first equation into each of the others. Now 
$$\begin{align*}
(\lambda+B0+C1)0+C0&=0+B00+C10+C0\\
&=0+B00+C(\lambda+1)0\;,
\end{align*}$$
and similarly for the third equation, so we get the system
$$\begin{align*}
B&=0+B00+C(\lambda+1)0\\
C&=1+B(\lambda+0)1+C11\;.
\end{align*}$$
The $B00$ and $C11$ terms are very useful. From $B=X+B00$ we can deduce that $B$ can be (anything represented by) $X$, $X00$, $X(00)^2$, and so on — in short, $B=X(00)^*$, where $$X=0+C(\lambda+1)0=\big(\lambda+C(\lambda+1)\big)0\;.$$ Treating $C$ similarly, we can rewrite the system as
$$\begin{align*}
B&=\big(\lambda+C(\lambda+1)\big)0(00)^*\\
C&=\big(\lambda+B(\lambda+0)\big)1(11)^*\;.
\end{align*}$$
Now substitute the second equation into the first and vice versa:
$$\begin{align*}
B&=\Big(0+\big(\lambda+B(\lambda+0)\big)1(11)^*(\lambda+1)0\Big)(00)^*\\
C&=\Big(1+\big(\lambda+C(\lambda+1)\big)0(00)^*(\lambda+0)1\Big)(11)^*
\end{align*}$$
We can now expand the right-hand side of the first equation to get an equation of the form $B=X+BY$, which, as we saw earlier, can be rewritten $B=XY^*$:
$$\begin{align*}
B&=\Big(0+\big(\lambda+B(\lambda+0)\big)1(11)^*(\lambda+1)0\Big)(00)^*\\
&=0(00)^*+1(11)^*0(00)^*+1(11)^*10(00)^*+B\Big((\lambda+0)1(11)^*(\lambda+1)0(00)^*\Big)\\
&=\Big(\lambda+1(11)^*(\lambda+1)\Big)0(00)^*\Big((\lambda+0)1(11)^*(\lambda+1)0(00)^*\Big)^*\;.\tag{1}
\end{align*}$$
We’ve now eliminated $A,B$, and $C$ from the expression for $B$, and you can check against the DFA that the regular expression $(1)$ really does describe the words that end up in state $B$. (Note that I have not tried to simplify the expression; it’s likely that it can be simplified, perhaps quite significantly.)
Now see if you can follow this model to get a corresponding regular expression for $C$; the regular expression $B+C$ will then describe the language accepted by the DFA.
{"set_name": "stack_exchange", "score": 1, "question_id": 1205303}