# DFA to regular expression conversion

I was looking at the question How to convert finite automata to regular expressions? to convert DFA to regex.

The question, I was trying to solve is:

I have got the following equations:

$Q_0=aQ_0 \cup bQ_1 \cup \epsilon$

$Q_1=aQ_1 \cup bQ_1 \cup \epsilon$

When solved, we will get $Q_0=a^*b(a \cup b)^* \cup\ \epsilon$

But my doubt is that, in the DFA starting state is also the final state so, even if we dont give any $b$, it will be accepted, if we give some $a$. But in the regex we have $b$, instead of $b^*$. Why is it so? Is it because,we have that regex $\cup$ $\epsilon$ ?

• Your solution for the equations is wrong (well, clearly, because the regex is wrong. It doesn't accept e.g. $aa$, which it should). Can you detail how you solved the system? Mar 1, 2013 at 17:35
• On the first glance, I would say that your DFA accepts a very simple language, which you can easily express as a regular expression.
– Dan
Mar 1, 2013 at 18:29

I'll be using the solution to $Q = \alpha Q \cup \beta$ given by $Q = \alpha^* \beta$, essentially as you would go solving a system of linear equations by hand:

\begin{align*} Q_0 &= a Q_0 \cup b Q_1 \cup \epsilon \\ Q_1 &= (a \cup b) Q_1 \cup \epsilon \end{align*} From the first equation you have $Q_0 = a^* (b Q_1 \cup \epsilon)$, the second one reduces to $Q_1 = (a \cup b)^* \epsilon = (a \cup b)^*$. Replacing $Q_1$ in $Q_0$ gives: $$Q_0 = a^* (b (a \cup b)^* \cup \epsilon) = a^* b (a \cup b)^* \cup a^*$$

Every state and every item from the set $$\{a,b\}$$ has a transition to another state, and every state is an accepting state. Therefore, all states are equivalent and the regular expression (in your notation) is just $$(a ∪ b)^*$$.

The automaton in question is equivalent to the following Kleene Algebraic fixed-point system of inequations: $$A ≥ a A + b B + 1,\quad B ≥ a B + b B + 1,\quad A,$$ with the last item, $$A$$, indicating the starting expression. The least fixed point solution for $$(A,B)$$, substituted into the starting expression $$A$$ yields the regular expression in question.

As you noted, you can factor $$B$$: $$A ≥ a A + b B + 1,\quad B ≥ (a + b) B + 1,\quad A.$$ You can solve for $$B$$. In general, the least fixed point solution to $$x ≥ u x + v$$, in $$x$$, which is denoted $$μx·(ux + v)$$, in Kleene algebra, is just $$x = u^* v$$. Thus, the reduction: $$A ≥ a A + b B + 1,\quad B ≥ (a + b)^*,\quad A.$$ Upon substitution for $$B$$ and elimination, this reduces to: $$A ≥ a A + b (a + b)^* + 1,\quad A.$$ In a similar way, we find the solution for $$A$$: $$A ≥ a^* (b (a + b)^* + 1),\quad A,$$ and, upon substitution and elimination of $$A$$: $$a^* (b (a + b)^* + 1).$$

(Your mistake, as already noted in another reply, is that you had the equivalent of $$a^* b (a + b)^* + 1$$, instead of $$a^* (b (a + b)^* + 1)$$.)

Kleene-algebraic identities can be used, particularly $$(u + v)^* = u^* (v u^*)^*$$ and $$u^* = u u^* + 1$$, reducing this to \begin{align} a^* (b (a + b)^* + 1) &= a^* (b a^* (b a^*)^* + 1)\\ &= a^* (b a^*)^*\\ &= (a + b)^*, \end{align} or, in your notation $$(a ∪ b)^*$$.

The axioms cited in the linked article are sufficient to prove any and all Kleene-algebraic identities. They are equivalent to the following set of properties: $$(x + y) + z = x + (y + z),\quad x + 0 = x = 0 + x,\quad x + y = y + x,\quad x + x = x,\\ (xy)z = x(yz),\quad x 1 = x = 1 x,\quad p 0 q = 0,\quad p (x + y) q = p x q + p y q,\\ 0^* = 1,\quad μx·(a + bx + xc) = b^* a c^*.$$ (Edit: I put in $$0^* = 1$$, too, otherwise you have to split the least-fixed-point equation into $$μx·(a + bx) = b^* a$$ and $$μx·(a + xc) = a c^*$$.)

These axiomatizations come from 1994. Many texts - even now - are obsolete, still using frameworks from the 1960's and not including these more recent developments, which themselves are now over a generation past.

If you strengthen it by replacing the last axiom with $$p (μx·f(x)) q = \sup_{n≥0} p f^n(0) q,$$ where $$f^0(x) = x,\quad f^1(x) = f(x),\quad f^2(x) = f(f(x)),\quad f^3(x) = f(f(f(x))),\quad ⋯,$$ where $$f(x)$$ denotes an arbitrary Kleene-polynomial in $$x$$, then you get an axiomatization for fixed-point-closed Kleene algebras that is complete with respect to the algebra of context-free subsets; i.e. an algebra for "context-free" expressions: μ-continuous Chomsky Algebras.

This comes from the mid-2010's (2014, I believe) and was in 2018 proven equivalent to another axiomatization that arose in 2008 (the algebra of C-dioids), which used in place of the last property that (a) every context-free subset $$U$$ has a least upper bound $$\sup U$$, and (b) $$\sup \{p\}U\{q\} = p (\sup U) q$$, for context-free subsets $$U$$.