This is the fourth day of my participation in Gwen Challenge
theorem
In the theory of finite automata, it is the theorem that if L is a set accepted by uncertain finite automata, there exists a deterministic finite automata that accepts L.
algorithm
An algorithm called subset method is introduced, which can transform NFA into equivalent DFA
Let’s define two operations on state set I
The ε-closure(I) of state set I is defined as a set of states. It is the set of states that any state S in state set I can reach through any ε arc. Obviously, any element in state set I is a member of ε-closure(I).
A-arc transition of state set I (move(I,a)) : defined as a state set J, where J is the totality of all states that can be reached from a state in I through an A-arc.
For example,
- The initial subset family C is empty [] and is represented by a table
| A subset of | Is marked or not |
|---|---|
- Calculate ε-closure(0) and set T0 = ε-closure(0) = {0,1,2,4,7}.
| A subset of | Is marked or not |
|---|---|
| T0 = {0,1,2,4,7} | 0 |
- Mark T0,
Closure (move(T0,a)) = {1,2,3,4,6,7,8};
Closure (T2 = ε-closure(move(T0,b)) = {1,2,4,5,6,7});
| A subset of | Is marked or not |
|---|---|
| T0 = {0,1,2,4,7} | 1 |
| T1 = {1,2,3,4,6,7,8} | 0 |
| ,2,4,5,6,7 T2 = {1} | 0 |
- Mark T1,
The T3 = epsilon – closure (move) (T1, a) =,2,3,4,6,7,8 {1}, namely the T1, T1 is in C
Closure (move(T1,b)) = {1,2,4,5,6,7};
| A subset of | Is marked or not |
|---|---|
| T0 = {0,1,2,4,7} | 1 |
| T1 = {1,2,3,4,6,7,8} | 1 |
| ,2,4,5,6,7 T2 = {1} | 0 |
| ,2,4,5,6,7,9 T3 = {1} | 0 |
- Mark T2,
The T4 = epsilon – closure (move) (T2, a) =,2,3,4,6,7,8 {1}, namely the T1, T1 is in C
The T4 = epsilon – closure (move (T2, b)) =,2,4,5,6,7 {1}, namely T2, T2 have in C
| A subset of | Is marked or not |
|---|---|
| T0 = {0,1,2,4,7} | 1 |
| T1 = {1,2,3,4,6,7,8} | 1 |
| ,2,4,5,6,7 T2 = {1} | 1 |
| ,2,4,5,6,7,9 T3 = {1} | 0 |
- Mark T3,
The T4 = epsilon – closure (move) (T3, a) =,2,3,4,6,7,8 {1}, namely the T1, T1 is in C
Closure (move(T3,b)) = {1,2,4,5,6,7,10};
| A subset of | Is marked or not |
|---|---|
| T0 = {0,1,2,4,7} | 1 |
| T1 = {1,2,3,4,6,7,8} | 1 |
| ,2,4,5,6,7 T2 = {1} | 1 |
| ,2,4,5,6,7,9 T3 = {1} | 1 |
| ,2,4,5,6,7,10 T4 = {1} | 0 |
- Marker T4,
The T4 = epsilon – closure (move) (T4, a) =,2,3,4,6,7,8 {1}, namely the T1, T1 is in C
The T4 = epsilon – closure (move (T4, b)) =,2,4,5,6,7 {1}, namely T2, T2 have in C
| A subset of | Is marked or not |
|---|---|
| T0 = {0,1,2,4,7} | 1 |
| T1 = {1,2,3,4,6,7,8} | 1 |
| ,2,4,5,6,7 T2 = {1} | 1 |
| ,2,4,5,6,7,9 T3 = {1} | 1 |
| ,2,4,5,6,7,10 T4 = {1} | 1 |
All subsets in C have been labeled, and the algorithm is over. Five subsets are constructed
,1,2,4,7 T0 = {0} T1 =,2,3,4,6,7,8 {1} T2 =,2,4,5,6,7 {1} T3, T4,2,4,5,6,7,9 {1} = =,2,4,5,6,7,10 {1}
Then the DFA M constructed by NFA N in FIG. 3.6 is as follows:
(1) S = {[T0],[T1],[T2],[T3],[T4]}
(2) the ∑ = {a, b}
(3)
D([T0],a)=[T1]
D([T0],b)=[T2]
D([T1],a)=[T1]
D([T1],b)=[T3]
D([T2],a)=[T1]
D([T2],b)=[T2]
D([T3],a)=[T1]
D([T3],b)=[T4]
D([T4],a)=[T1]
D([T4],b)=[T2]
(4) S0=[T0]
(5) ST=[T4]
To facilitate writing, rename [T0],[T1],[T2],[T3],[T4] and represent them as 0, 1, 2, 3, and 4 respectively. The state transition diagram of DFA M is shown in FIG. 3.8
conclusion
Subset method simply means adding the first subset of subset family C by ε-closure(0).
Traversal of subsets in subset C.
For each unlabeled subset Ti, mark Ti first, and then perform ε-closure(move(Ti, I)) operation for each input character I of Ti.
If the operation produces a new subset, the new subset is added to the subset family C.
If all members of C are labeled, the algorithm ends.