Please help me covert the dfa to regular expression

Question

i don't know how to use algorithm to covert this dfa to regular expression. Please help me.

Answer 1

Assuming that this notation indicates that (1) is both the initial and only accepting state, the transition table for this automaton is:

 q     s     q'
(1)    a    (3)
(1)    b    (2)
(2)    a    (1)
(3)    a    (2)
(3)    b    (3)

Let r, s and t be the regular expressions which lead to (1), (2) and (3). Then

r = e + sa
s = rb + ta
t = ra + tb

We can begin iteratively solving this system. First, we see the self-reference in the expression for t, and we can remove if with the rule x = y + xz <=> x = yz*:

r = e + sa
s = rb + ta
t = rab*

Now we can get rid of t by substituting in the first two lines:

r = e + sa
s = rb + rab*a

Now we need an expression for r, so we might as well bite the bullet and sub in the expression for s in line one:

r = e + (rb + rab*a)a
  = e + rba + rab*aa
  = e + r(ba + ab*aa)

From our rule, we further reduce:

r = (e)(ba + ab*aa)*
  = (ba + ab*aa)*

Spot checking suggests this regular expression is correct. If you accept the validity of the following rules for reducing expressions involving regular expressions (i.e., prove them or accept them without proof), the derivation constitutes a valid proof of the regular expression:

rule 1: x = y + xz IFF x = yz*
rule 2: w = xy AND x = z IFF w = zy
rule 3: w = x + y AND x = z IFF w = z + y

The interpretation given to equality above is this: the LHS is equal to the RHS if and only if the language of the LHS is equivalent to the language of the RHS. While (0+1)(0+1) and 00+01+10+11 are different regular expressions, they generate the same language of four strings and therefore are equal for the purposes of discussion.