enter image description here

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?

  • $\begingroup$ I'm so sorrry the picture did not get uploaded. I'm uploading it again $\endgroup$
    – Pants
    Oct 17 '15 at 20:48
  • $\begingroup$ You don’t have enough ‘reputation’ to incorporate a picture, so I’ve done it for you. $\endgroup$ Oct 17 '15 at 20:49
  • $\begingroup$ 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). $\endgroup$
    – BrianO
    Oct 17 '15 at 21:11
  • $\begingroup$ Thanks @BrianO that helped a lot. I wasn't aware that you can use 'or' in RE's. $\endgroup$
    – Pants
    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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.