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?
On
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^*.$$
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
any number of times (including none), and finally go to state $2$ and possibly spin our wheels there for a while.