The algorithm Called Subset Construction The E-closure of a set of states The E-closure of a single state s is the set of states reachable by a series of zero or more E-transitions and we write this set as. S Example 2. 14 regular a*
The Algorithm Called Subset Construction. • The -closure of a Set of states: – The -closure of a single state s is the set of states reachable by a series of zero or more -transitions, and we write this set as . • Example 2.14: regular a* s a 1 2 3 4
The algorithm called subset construction 1={1,2,4},2={2},3={2,3,4},and4={4} The 8-closure of a set of states the union of the e-closures of each individual state 1,3}=13={1,2,3}{2,3,4}={1,2,3,4}
The algorithm called subset construction. a 1 2 3 4
The subset Construction Algorithm (1)Compute the s-closure of the start state of M; to obtain new state M (2)For this set, and for each subsequent set, compute transitions on characters a as follows Given a set s of states and a character a in the alphabet Compute the set a=t for some s in S there is a transition from s to t on a Then, compute Sa, the E-closure of S This defines a new state in the subset construction together with a new transition s→)S (3) Continue with this process until no new states or transitions are created (4) Mark as accepting those states constructed in this manner that contain an accepting state of m
The Subset Construction Algorithm
Examples of subset construction M8-closure ofM(S)s 2.4 3234 1,2,4} 2,34}
Examples of Subset Construction a 1 2 3 4 M -closure of M ( S ) S a 1 1,2,4 3 3 2,3,4 3 a a {1,2,4} {2,3,4}
Examples of subset Construction N G-closure ofM(S)S 1,2,6 3.7 3.7 3.4.78 5.8 1,2,6 (B4781)(8
Examples of Subset Construction 4 a 2 3 b 1 5 6 7 a M -closure of M (S) S a S b 1 1,2,6 3,7 3,7 3,4,7,8 5 5 5,8 {1,2,6} b {3,4,7,8} {5,8} a