Conversion of DFA to Regular expression
Conversion of DFA to Regular expression
To convert the DFA to Regular Expression (RE), we are going to use a method called converting DFA to regular expression by eliminating states. This method is used to obtain Regular Expression from the given DFA.
Algorithm
The algorithm steps for converting DFA to regular expression by eliminating states is given below:
- If the finite automata does not contain unique initial and final state, then create two new states (one is initial and other is final). Now make original final states as non-final state and original initial states as non-initial state by adding ?-transitions from each of the new state to the corresponding initial or final state.
- Remove states one by one except initial and final state.
Suppose, we are eliminating state E which is between states D and F. when we remove state E, all the paths that went through E will no longer exist in the finite automata. The label from state D to state F now include strings rather than single symbols, and there is a simple way to represent all these strings with the help of regular expression. This means that the label from state D to state F now contains a regular expression.
- When two states are joined by more than one edge going in same direction then we can write them on single arc specifying union of the labels of all the edges.
- After removing all the states except initial and final state we are left with the final regular expression on the label of initial and final state.
Now let us discuss some cases that help in converting finite automata to regular expression.
Case 1: Suppose we have a state S of the finite automata M as shown below:
We can replace the loops with one loop labelled with the union of all the labels
The state can be represented as:
Case 2: Suppose two states S1 and S2 of finite automata are connected by more than one edges going in the same direction.
We can replace all the edges with single edge labelled the union of all the edges:
Case 3: Suppose three states of finite automata are connected in row as shown below:
Here, we can eliminate the middle state resulting in two states S3 and S5 whose label is the concatenation of the labels from S3 to S4 and S4 to S5.
Case 4: If in case 3, the state S4 contains a self-loop as shown below:
We can eliminate state S4 and the label from state S3 to S5 will contain r1r3*r2 as shown below:
Similarly if have this type of loop in finite automata
After eliminating S8 state in above finite automata, we have:
Case 5: If we have finite automata having more than one initial state and final state, then we can convert it to the finite automata without changing the language it accepts.
For Example:
We can modify it as shown in following figure:
Case 6: If we have a finite-automata as shown below:
The regular expression for the accepted strings can be described in various ways
Regular expression is (0+ 1)* 100 (0+10)
Example
Convert the following finite automata to regular expression.
Solution:
In above finite automata we have unique initial state but two final states q4 and q6.
So, we first convert this finite automata with final states to finite automata with single final state by creating new final state qf with ?-transitions to the state q4 and q6.
After converting this the finite automata we have
Now next step is to remove states one by one. Firstly remove state q1.
After eliminating state q1 in finite state we have
After eliminating state q2 in finite state we have
Now we can eliminate state q5. After elimination of state q5 in finite automata we have
Now we can eliminate state q4 and q6. After elimination of state q4 and q6 in finite automata we have
After modifying some changes in above finite automata we can write this finite automata as:
After eliminating the state q3 in finite automata we have
The final regular expression of given finite automata can be written as:
After converting the finite automata to Regular expression. The converted regular expression is (0+ 1)* 100 (0+10).