HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

DFA to regular expression conversion

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
expressionconversiondfaregular

Problem

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

Solution

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

Context

StackExchange Computer Science Q#10180, answer score: 2

Revisions (0)

No revisions yet.