II Transforming regular expressions into finite state automata: NFA state machine recognizes input strings

original text :https://study.163.com/course/courseMain.htm?courseId=1002830012
Given a regular expression ：D*.D | D.D*
Use the program we developed in the previous sections , Build the corresponding... For the above regular expression NFA State machine , The constructed state machine is as follows （ Show the original ）：

We will use the above NFA To identify the string 1.2.
In the diagram above , Last state 18, Because there is no way out , therefore , state 18 Is the receiving status .

We go from state to state 17 Start , Remember we said before , Corresponding to ε edge , The state machine can enter automatically without any input characters ε The next state the edge points to . thus , From the State 17, At the same time, we can enter the State ：3, 1, 4, 9, 5. A collection of these states , To be exact , Corresponding to a given set of initial states , Through their ε A collection of states that an edge can achieve , We call it ε Closure , Remember to do ε-Closure. Because according to the initial state 17, adopt ε edge , The states we can reach are 3,1,4,9, therefore ：
ε-Closure({17}) = { 5,9,17,1,3,4 }

Attention, everyone ,ε In closure collection , Contains the given initial state , Because for any state , It can reach itself without entering any characters , therefore , We default to , Every point implies a path from oneself to oneself ε edge , So it's calculating ε Closure time , The result must include the input state set when calculating the closure , That's why the right side of the above equation contains States 17.

From the input , Read in character 1 after , Get the jump status from ε Find... In the closure collection , From the picture we find , Can read characters 1 The state of , Is the state in the closure set 1,9. From the State 1 Read in character 1 After entering the State 2, From the State 9 Read character 1 After entering the State 10, state 2 and 10 We call it a set of transition states , Write it down as ：
move({5,9,17,1,3,4}, ‘1’) = {2, 10}

Next , We are in a state of 2,10 Conduct ε Closure operations , That is to see ,2,10 adopt ε What states can an edge reach ：
ε-Closure({2, 10}) = { 10,5,2,11,1,4 }.

The next character we read in is . , Look at the transition set after the input point from the closure set above , According to the state diagram , We learned that , state 5 Input . After entering the State 6, state 11 Receive character . After entering the State 12, So we have ：
move({ 10,5,2,11,1,4 }, ‘.’)= { 6,12 }
then , We do this for the transfer set ε Closure operation has ：
ε-Closure( 6,12 ) = { 6,12,7,18,16,13,15 }
Attention, everyone , At this point, the closure set contains the receive status 18, It also means that , A string of currently entered characters 1. It can be accepted by our state machine . But because the input has not been processed , So we continue to input unprocessed characters into the state machine , The current character to be entered is 2, therefore ：
move({ 6,12,7,18,16,13,15 }, ‘2’)= { 14,8 }
To transfer sets {14,8} Doing closure operations has ：
ε-Closure( 14,8 ) = { 14,8,18,16,13 }
here , The closure collection contains the acceptance status 18.

here , All characters have been processed , At the same time, the state machine enters the accept state , So strings 1.2 Can be our NFA Accepted by the state machine .