3
$\begingroup$

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:

enter image description here

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$ ?

$\endgroup$
2
  • 3
    $\begingroup$ 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? $\endgroup$
    – Shaull
    Mar 1, 2013 at 17:35
  • $\begingroup$ On the first glance, I would say that your DFA accepts a very simple language, which you can easily express as a regular expression. $\endgroup$
    – Dan
    Mar 1, 2013 at 18:29

2 Answers 2

2
$\begingroup$

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^* $$

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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