patternMinor
DFA to regular expression conversion
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$ ?
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^*
$$
$$
\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.