Week 11

We use to deal with the DFSA which stands for determined finite state automaton. In some cases the string doesn't always proceed into one state, as such we have the non-determined FSA concepts introduced in. The NFSA is defined in a similar way as DFSA, which still holds Q as a finite set of states, the \Sigma is a finite alphabet, and the \delta which was defined in a more weird way, it was Q * (\Sigma \union {\epsilon}) \implies P(Q). The rest are what we have in DFSA: s\in Q as the starting state, F \in Q as the accepting state. We can somehow transform a NFSA into a DFSA. So there is a "theory": every NFSA has a equivalent DFSA. For regular expressions, we got a NFSA to represent every regular expression as well.

After that we experienced the process of transferring a NFSA to a regular expression. We first add \epsilon state to it, and then begin to cut off any state as we please. Usually through this state you can travel to certain states via certain paths. Mark these path down and we have got the regular expression. For example if it takes a string 1 to go to another state and a string 0 to come back, we will have a string 10 as its path. After we cut off this state, all paths with destinations to itself will be derived to a self-loop of another state. The path we marked down earlier will become its self loop condition. As we repeat this process, we will eventually have two states left with a whole bunch of regular expression as the bridge between the two. One is the starting state and anther is the accepting state. By the end of the lecture we also realized that there is some kind of language that is hard to denote using our current method. Like the binary string with the same numbers of 1 and 0.