Regular expresions (RE) can be converted to NFA and then to the equivalent DFA.
Note that NFAs and DFAs are equal and every NFA can be converted into a DFA.
The first step is to convert RE to NFA. For this, we require a stack to store the states.
We traverse the RE from left to right.
1) If we come across an operand (like 0, 1, a, b etc), create 2 new states, Make 1 transition and 1 push into the stack.
eg 0
2) If we come across a concatenation sign (.), pop 2 states from the stack, there is 1 ε (nothing) transition and 1 push.
eg 0.1
3) If we come across a union (+), pop 2 states from the stack, add 2 new states, make 4 ε (nothing) transitions and 1 push.
eg 0+1
4) If we come across a Kleene’s closure (*) pop 1 state, add 2 new states, make 4 ε (nothing) transitions and 1 push.
eg 1*
5) If we come across a positive closure (+) pop 1 state, add 2 new states, make 3 ε (nothing) transitions and 1 push.
eg 0+
The Priority is
The first step is to convert the RE to postfix
For example to convert RE = ((0+1).(0+1))* to NFA
Postfix = 01 + 01 + . *
First we come across an operand, so make 2 states and push them in the stack.
Next we have a 1, so we repeat the same process with new states.
Next there is an OR (+) so we pop 2 states, add 2 new states, make 4 ε (nothing) transitions and 1 push.
Again we have 0 and 1, so me make 2 new states and push them.
Then we have an OR (+) so we pop 2 states, add 2 new states, make 4 ε (nothing) transitions and 1 push.
Then we have a concatenation sign (.) so we pop 2 states, make 1 ε (nothing) transitions and 1 push.
Then we have a Kleene’s Closure (*) , so make 1 pop, add 2 new states, make 4 ε (nothing) transitions and 1 push.
Now we have reached the end, so whatever is left in the stack become the first and last state.
This is the final NFA.
Now to convert this NFA to DFA, convert the NFA diagram into a table as follows,
0 | 1 | ε | |
1 | 2 | ||
2 | 6 | ||
3 | 4 | ||
4 | 6 | ||
5 | |||
6 | 1,3 | ||
7 | 8 | ||
8 | 12 | ||
9 | 10 | ||
10 | 12 | ||
11 | 7,9 | ||
12 | 14,5 | ||
13 | 5,14 | ||
14 |
Here 13 is the starting state, so we start from 13 and see all the ε closures of 13
(all the states u can reach on an epsilon (ε) from 13 ). If any of the states in the epsilon closure reach to a 1 or 0 we make them the next states where we can reach on a 1 or 0.
In the above example,
states | ε closure | 0 | 1 |
13 | 5, 14, 1 , 3 | 2 | 4 |
2 | 6, 11, 7, 9 | 8 | 10 |
4 | 6, 11, 7, 9 | 8 | 10 |
8 | 12, 14, 5, 1, 3 | 2 | 4 |
10 | 12, 14, 5, 1, 3 | 2 | 4 |
All states that have ε closure as any of the final states, become final states, therefore 13, 8 and 10 become final states. 13 is also the start state. Here states 2 and 4 go to the same states and both are non final states, so they can be merged into 1 state. Also 13,8 and 10 all go to the same states on 0 and 1 and all are final states (Note: They cannot be merged if ALL states are not final or non final states) so they can be merged into one state. Therefore the final DFA is
Feel free to comment if you have any doubts.
Recommended articles:
Comments
Post a Comment