Note that this is going to match CANDAN only if my data pattern,

data sequence is exactly CANDAN.

Now, let's assume that we want to allow one insertion.

That is basically if the data is CAANDAN where there is one insertions,

I still want to be able to match that.

Well, what we can do, is we can basically create

a non-deterministic finite automata that supports that one insertion.

So, in this case,

my non-deterministic finite state automata looks like this.

It is very similar to the original finite state automata,

but it has one more layer.

And these layers are connected with a star edge,

well, it's actually a star edge matches any symbol in my alphabet.

So, how can this be used?

Let's see our data sequence CAANDN.

So, how will this match?

Well, lets start from C. So,

C from the beginning is going to bring us to this state.

At that position, we have the next symbol A.

So, the next symbol A, in this case,

is a non-deterministic finite state automata.

It's not going to bring us only to this position where we have seen CA,

but also bring us to this position where we have seen CA.

So, for the non-deterministic finite state automata with the prefix CA,

I am at two states,

not only one state.

Then I see another A.

Here it fails because if to you follow at that layer,

the next symbol should have been N, so it fails.

This means that I go back to the start.

However, at this point position,

I can actually follow A and I can come to the state where I have seen CAA.

And note that if you follow over the next sequences,

N is going to bring you this state,

D is going to bring you this state,

the next A is going to be in this state,

and the final N that you will consume will bring you to the success state.

Note that, what happens that I have matched CAANDAN.

If the input sequence was CANDAAN,

I could also match that. How would that work?

In that case I would've started at C,

then I would have consumed an A,

then I would've consumed an N,

then I would have consumed a D,

then I would have consumed an A,

then I would have consumed another A,

and then finally, I would consume N and I will match that.

So, this two-layer non-deterministic finite set automata,

is actually is going to match any one inversion exactly.