# How to convert DFA into RE?

So I am trying to convert this DFA into an Regular Expression. I got an answer but I am not 100% is correct I feel like it is too long. From my understanding, I just need to find the transitions into the accepting state and write them in an expression.

I got
L(1,1,0) = a*
L(1,2,0 = b
L(1,2,1) = a* b
L(2,2,0) = a*
L(2,2,1) = (ba* b)* a loop

so in the end I got
b U (a* b)U(a * b)a U (a * ba * ba * b)*

I feel like this is too long for an answer... is this even correct?

• I'm so sorrry the picture did not get uploaded. I'm uploading it again Oct 17 '15 at 20:48
• You don’t have enough ‘reputation’ to incorporate a picture, so I’ve done it for you. Oct 17 '15 at 20:49
• Every string recognized by your RE ends either in 'b' or in a single 'a'. But 'baa' is in the language accepted by the DFA. I get $a^{*} b a^{*} + (b a^{*} b a^{*})^{*}$ -- that is, $r + (b r)^{*}$ where $r = a^{*}ba^{*}$, by looking at the diagram (no formal conversion procedure used). Oct 17 '15 at 21:11
• Thanks @BrianO that helped a lot. I wasn't aware that you can use 'or' in RE's. Oct 18 '15 at 19:18

This DFA is simple enough that we can do it ‘by eye’ rather than by an algorithm. It’s clear that we need an odd number of $b$s in order for a word to be accepted: an even number leaves us in state $1$, while an odd number puts us in state $2$. Reading $a$s never changes the state. Thus, any word that’s accepted must end in $ba^*$. Before that it can have any even number of $b$s interspersed arbitrarily with any number of $a$s, and we might as well assume that it ends up in state $1$. That means that it can repeat $a^*ba^*b$ any number of times, so $(a^*ba^*b)^*ba^*$ almost works – ‘almost’ because it misses the words with just one $b$ that begin with $a$. We could add these with a union, but there’s a slicker solution: $a^*(ba^*ba^*)^*ba^*$.

In other words, we can spin our wheels as long as we like in state $1$, then repeat the process

go to state $2$, optionally spin our wheels, go back to state $1$, and optionally spin our wheels

any number of times (including none), and finally go to state $2$ and possibly spin our wheels there for a while.

• I went back to this question. Isn't this starting me with bbb? Oct 18 '15 at 19:16
• @Jean: No: $a^*(ba^*ba^*)^*ba^*$ allows the parenthesized segment to appear $0$ times, so everthing matching $a^*ba^*$ is accepted. Oct 18 '15 at 19:21
• Thanks for the quick response! @Brian M. Scott Oct 18 '15 at 19:22
• @Jean: You’re welcome! Oct 18 '15 at 19:26

DFA to RE conversion can be done systematically, using what is essentially linear algebra. For each $i$, let $L_i$ be the language of words starting in state $i$ and ending in an accept state. The DFA gives us the following system of "linear equations" in the $L_i$'s: $$\begin{eqnarray} L_1 &=& a L_1 + b L_2\\ L_2 &=& b L_1 + a L_2 + \epsilon\\ \end{eqnarray}$$ where $\epsilon$ denotes the language consisting of just the empty word, and $+$ is union. (For example, a word in $L_2$ either starts with $a$ (in which case what's left over is in $L_2$), with $b$ (in which case what's left over is in $L_1$) or is empty (since $2$ is an accept state).)

These equations can be solved by successively eliminating all $L_i$'s other than $L_1$, which is the one we want since $1$ is the initial state. The key fact which makes this easy is the following: if $A$ and $B$ are languages, then the unique language $X$ satisfying $X=AX+B$ is $X=A^*B$.

We start by eliminating $L_2$ using the last equation; the key fact tells us $$L_2=a^*(b L_1+\epsilon).$$ Thus the first equation becomes $L_1=a L_1+ ba^*(b L_1+\epsilon)=(a+ba^*b)L_1+ba^*$, whence $$L_1=(a+ba^*b)^*ba^*.$$