Now, first we're going to look at the process of simulating the operation of an

NFA. And in order to do that, we have to look at the representation. so for state

names we're just going to use the integers from zero to N and those are just indexes

into the regular expression strain with one extra one for the except state. So, if

RE has M characters, we've got M plus one states. and then, we forget the

match-transitions. so for with this, we'll just keep the regular expression in an

array. and then for characters that are not metacharacters that are just

characters from the alphabet there's match-transition just to the next element

just to add one, so that's an implicit representation of the match-transitions.

and then the next thing is the epsilon transitions. So, since there might be

multiple edges leaving from any given state and it is directed, it always says,

go from this state to another one we'll use directed graph. So we just have a

bunch of edges with given vertex names. And that's convenient. That's what we use

for our graph processing algorithms, was indexes for vertex names. so, this is

totally well-suited to building a digraph using the basic digraph processing methods

that we talked about when doing graph processing. so, that's our representation

and then given that representation it's very, you know, straightforward to find

out for any state what are the possible next states and if it's got a character in

a possible next state is to match a character in angle up one otherwise it's

the vertices that they are pointed to by the edges and its adjacency list does have

epsilon transitions. So, let's take a look at just given that basic idea, that we can

always get to the transition from any given state how we're going to do a

simulation? and so, the idea is summarized by this diagram here. what, what we're

going to do is at every step each text character that the machine does read,

we're going to keep track of the, the set of all possible states where the NFA could

be after reading in the i, I text ch aracter.

So, say, we've done that and, you know, there's this is just a schematic. So,

there's a bunch of states that we could get to after reading i characters. Now in

some of those states they, they are labeled with characters. and if that

character matches our text character, they can take us to another state. So, say, in

this case, there is three of them that matches and the other one has some other

character or different character and it couldn't take us to another state. So,

that gives us a all the possible states that you could be in just after reading

the i plus first symbol. And now, what we do is take a look at the possible null

transitions that we could go to from those states. And that might take us to lots of

other states. but that's all the machine could do. It could read a character. And

then it can take a bunch of null transitions. and but that's all it knows

how to do. And that will give us all the possible states that it could be in after

reading i1 plus one symbols. And then, we just continue in that from every one of

those states. some of them match the character match the character, and then,

look at all the epsilon transitions. So, that's the basic idea is to simply keep

track of all possible states the NFA could be in after reading the first i text

characters. so the only thing that's complicated is how do we get all the

states that we could reach by epsilon transition. and we'll look at that in just

a second. It's actually very straightforward. But let's look at a demo

first. so this is our machine for A<i>B or A, or AC followed by D. and let's suppose</i>

it has this input. So, let's do this demo. Okay. So, we're going to, to check if the

input is matching the pattern. we're going to start the machine in state zero and so

the zero is one of the states, you could reach from the start. and then now we want

to get to all the states that you could reach by epsilon transitions from the

start. and so there's a bunch of them so we could go to one and from one, we could

go to either two or six. from two, we could go to three. From three, we could go

to two or four. so we could get to all those places from the start without

scanning a single character. So, zero, one, two, three, four, and six the machine

could be in any one of those states before it scans a single character. so, that's

where it could be after zero characters. But what about now after the first

character? Well, out of those states only two and six involve matching an A. So the

only thing that could happen next to read, the machine could do next, is to read the

A in either state two or state six. I know there's going to be match-transitions. So

in the first case, it goes to three and, and the second case, it goes to seven. So,

the stead of states, it can be reachable just after matching the A, is just three

and seven. But now from those states it might get somewhere with epsilon

transitions. We have to look at the epsilon transition graphs and what states

could it go to from epsilon transitions from these two. well, from three, seven

has nowhere to go, and from three it could go either to two or four. from two, it

could go back to three so the total number states that it could be after matching A

is two, three, four, and seven. and so that's one step. We've matched one

character, and we have kept track of all possible states the machine could be in

after matching that character. Now, what about the next character? You can see,

these four states take us all different ways. You could have an A, a B, or a C

next, and it could get somewhere. But it happens, we have an A, and the only one of

these states that matches an A is two. So, after matching the second A the only place

it could get to is three. and so that now, we have only one state to work with. But

where could we get with via epsilon transitions, from three? and so, well, you

can go from three to four or two. Well, we did this before. And then, from two back

to three. So, we could be in two, three, or four after matching two As. so that's

all the possible states we could be in after mat ch, after matching the two As.

now, what's next is B, only state four matches to B, so the only place we could

be right after matching the B is in state five. And that's after matching the B, now

what about epsilon transitions? Well, state five has an epsilon transition to

state eight. so we could take that one and eight has got one to nine. So it could be

an either five, eight, or nine after matching AAB and then following all of the

epsilon transitions. but its really important to keep in mind, there's no

other state the machine could be and it doesn't have any other way to get to after

matching AAB it couldn't get state seven or six or two. those are the only possible

states it could be in. since we're, each time, progressing through the input we're