So the final step in our regular refreshing pattern matching algorithm is to construct and then determine the thick finite automaton. So how do we go ahead and do that? and this is an integral part of the algorithm. but we pretty much have got all the pieces, but really what makes it intricate is that if, an illustration of what a programming line has to do to when trying understand your program, what your programming does. What we need to do is somehow understand what's in the regular expression and then take that information and use it to build the machine. Now, that's what parson, that's called parsoning. to try to figure out the structure of your program or regular expression and then, do something with it. And this is a simple example of that but useful as well. So the first thing that needs clear what to do. So we're going to have one state per character as we talked about before, so that's easy to set up. and then the match transition edges. if a state contains a character in the alphabet, we just put in a match transition to the next state. and actually, that's implicit in our algorithm. so now what about other things? Well, if we have for any parenthesis we find, we'll just put in an epsilon transition to the next state. so our machines all have that. now closure is one that you know, has quite a bit of action. so, for every star let's look at the one that is just a one character closure. So we have a single character closure. So this is A star. and, and what we need is epsilon transitions for the star that allow the machine to go and pick up well, there has, there has to be one, an epsilon transition that goes out to the star to cover the case, so we have zero matches. and then after zero, then we want to go back to have as many matches as we want before taking the sorry, take the match transition. We're going to be able to go back and match as many as we want before going up to the next. So for star, we have to add three epsilon transitions. The one that goes if you have a character in I and a star in I + one , you have to add these edges going both ways and then an edge out to the next character for, to get out of the star. And that works also if there's a closure involving parentheses. If the character before the star is a parenthesis then we want to add the same kind of mechanism from the parenthesis, go out and skip the whole thing to cover the zero match case or go back and match as many times as we need to match and then finally, go out. So there's three edges have to be added for each star and defined and well defined what they are. and then or there's two epsilon transition edges that we have to add. and that is to allow the machine to skip the first part of the expression and do the second or to skip the, do the first part of the expression and skp the second. so if we keep track of where the left parenthesis is when we end the or operator when we get to the right parenthesis, we have all the information that we need in order to be able to add those two edges. so those are the edges that we have to put together to build the NFA. and the trick is keeping track of the information of where the previous operators are particularly since parentheses can be nested. but this is not that difficult to do because we have a mechanism for doing that. how to, to, remember where the left parentheses are and, and the or and that's to maintain a push down stack. and so the, the algorithm is to push left parenthesis in or onto the stack. And then when we hit right parenthesis, then we can pop of course the corresponding left parenthesis and maybe, maybe the or and that gives us all the information that we need to add the epsilon transition edges and so the stack takes care of the nesting of the parenthesis. and when you think about it, this is a very natural mechanism to use very similar to the early programs that we wrote using Dexter's algorithms for medic expressions. so let's look at a demo and you'll see how that works. So we're going to build the machine corresponding to this regular expression and it's the one that we've been working with. And so what we do is just go from left to right through the regular expression and , take the appropriate action, for each character. So for left parenthesis. there's always an epsilon transition from, left parenthesis to the next state. and then the other thing is, if you remember that last parenthesis on the push down stack. So we put the index zero onto the stack. so now we got another left parenthesis again, we put the epsilon transition on, and we push that one onto the stack. so now, if we have an alphabet symbol what we need to do is add the match transition to the next state. And then there's a couple ways to this, but one easy way, in this case, is to just look for the star and if you see that the next one is a star then you've got everything you need for the epsilon transitions. So, in this case the next one is a star so we'll add those epsilon transitions from the from two to three and from three to two. And adding epsilon transitions, that's just, adding edges to the phi graph. then with closure that just takes us to the next state and we took care of the other two earlier. now we have an alphabet symbol, that's the B, so we just put in the transition to the next state. Now we have an or. All we do for an or is put it on the stack. now it's got for A, we got the match transition, for C, we got the match transition. and now we have the first right parenthesis. so this right parenthesis so one thing we, the first thing we do is an epsilon period just to get it over to the next state. but then we go to the put down stack and we pop. and if the thing at the top of the stack is an or that's one thing, piece information that we need. the other piece of information we need is the position of the corresponding left parenthesis and that'll be the next thing on the stack. So we add the transition we pop the or off the stack and we pop the or on and off the stack and that gives us the information that we need to put in the epsilon transition. We're at stage eight. We put one from the or to eight, and then we put one from the one to the or + one. There's the, that's what we need to do. and, look for a star the same way as we did for one character. now in this case we have a no star. So we just do the finite alphabet symbol and we add the match transition. and now we have the right parenthesis and so we pop the corresponding left parenthesis. and it's not an or. so in this case you know, there's nothing to do except do the epsilon transition to the accept state. so that's the process for each character in the regular expression, it's well defined what we do. left parenthesis and or we put onto the stack characters we do the match transitions and right parenthesis we do a pop and if it's an or, put a numeric transitions. otherwise we do the look at to check for the star. and that's the demo of the construction for nondeterministic finite state of phenomena. So, it's actually a remarkably simple process. we figured out what to do with each character in the regular expression and this is the second part of the regular expression pattern-matching algorithm, which is constructing the NFA. And again it's a remarkably little code. So it's a routine that builds the epsilon transition. this is a part of the NFA. So it's got the regular expression . yes, a useless variable to refer to. and it's going to build a new diagraph with one state, one extra state, the accept state M+11 if the rate description has M characters. so, the and then we maintain a stack which is just integers. and for every character in a regular expression we do the processing that we just described. if it's a left parenthesis or an or we just put it on to the stack. and that's it. if it's a right parenthesis then we pop. If that pop is an or, then we put in the two edges to skip the or. and otherwise, we look ahead and do the closure exactly as described. If it's any one of the metal symbols, we just put in a next line transition to the next edge. And then a remarkably little code to go ahead and construct the NFA from a given regular expression. and so, the final step is the analysis that's going to take time and space proportional to M. and that's immediate, because for every character we do most of two stack operations and add at most three epsilon transitions. And, this is a generous upper bound, time and space proportional to the number of characters in the regular expression. So that's how we get the NFA