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

Convert DFA to Regular Expression

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

Problem

In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q_2$ state is eliminated first.
The provided solution to eliminate $q_2$ is:

If we first eliminate $q_2$ we obtain an intermediate automata with $3$ states
$(q_0$,$q_1,q_3)$ such that:



  • We go from $q_0$ to $q_1$ with RE $a+ba$



  • We go from $q_0$ to $q_3$ with RE $bb$



  • We go from $q_1$ to $q_1$ with RE $ba$



  • We go from $q_1$ to $q_3$ with RE $a+bb$




I don't understand nr2. $q_3$ can also be reached using RE $aa$. Why is this left out?

:

:

Solution

The conversion in each step forms REs that describe

  • The previous direct edge from one state to another and



  • the path(s) that use(s) only the removed state as an intermediate state.



In your example, the path for $aa$ goes through $q_1$, which is not removed in this step. Thus it is not added to the RE.

Context

StackExchange Computer Science Q#28517, answer score: 8

Revisions (0)

No revisions yet.