snippetMinor
Convert DFA to Regular Expression
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:
I don't understand nr2. $q_3$ can also be reached using RE $aa$. Why is this left out?
:
:
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
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.
- 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.