Download project documentation

ExTab 2-8C: DFA transition matrix
Starting with D column, states 0, 1 and 4
all go to a state in partition 0 on a D, but
state 2 goes to partition 1 on a D, and
thus state 2 must be removed from
partition 0. Continuing in the same
manner, state 3 is also distinguished by a
D. Changes are illustrated in ExTab 28C.
D
State
0
1
4
2
3
5
6
7
1
4
4
3
6
7
7
.
2
5
2
-
Group
0
2
3
1
ExTab 2-8D: DFA transition matrix
Now, going down the dot (.) column, the
dot distinguishes state 1 from states 0 and
4 because state 1 goes to a state in
partition 1 on a dot, but states 0 and 4 go
to states in partition 2. The new partitions
are on the last column in ExTab 2-8D.
D
State
0
4
1
2
3
5
6
7
1
4
4
3
6
7
7
.
2
2
5
-
Group
0
4
2
3
1
ExTab 2-8E: DFA transition matrix
Going through the array a second time,
column by column, now D distinguishes
state 0 from state 4 because state 0 goes
to a state in partition 4 on a D, but state 4
goes to a state in partition 0 on a D, and
here no other states can be distinguished
from each other, so it's done. So the final
partition looks like ExTab 2-8E.
D
State
.
Group
0
1
2
0
4
4
2
5
1
2
3
5
6
7
4
3
6
7
7
5
-
4
2
3
1