
Title:
0158 Nondet To Det

Description:

Let's do one more bit of practice

converting nondeterministic machines to deterministic ones.

Here I've written a nondeterministic machine.

It has ambiguity.

Right in state 1 there are 2 ways to go on a.

It also has epsilon transitions,

and I'll start making its deterministic equivalent down here.

Well, when we enter the nondeterministic machine,

we could only be in state 1, but after that we could see an a,

and if I see an a I could be in 2, 4,

or I could take the free epsilon transition to 5,

or I could keep going and take the free epsilon transition to 6.

I'll label my new state 2456

because it keeps track of everywhere that I could have my fingers

if I'm simulating this nondeterministic machine.

Now, should this state be an accepting state or not?

Well, remember that a finite state machine accepts if there's any path

to an accepting state, and 6 is one of our accepting states.

Because the original machine could accept a,

a, epsilon, epsilon, win, we want our new machine to also accept a.

A, win.

In my converted world, the state accepts if any of its corresponding

original states also accept.

Let's say that I'm in either 2, 4, 5, or 6 and I see a c.

If I'm in 2 and I see a c, I fall off the world.

If I'm in 4, fall off the world.

5, I go to 6, looking good.

6, fall off the world.

Here if I was in 2, 4, 5, or 6 and I see a c,

I end up just in state 6, and that's definitely an accepting state.

Now, there's some other ways to get out of 2, 4, 5, and 6,

and when we do, we might be in states 2 or 3.

Since 3 is an accepting state up there,

2 or 3 is an accepting state down here.

If I'm in 2 or 3, on a b from 2 I go to 3,

and c I'd fall off the world, so we'd end up in state 3.

If I'm in 2 or 3 and I see a c,

I must really have been in state 3, and I stay in state 3,

so either on b or c we end up in just state 3,

which is also an accepting state.

And if I'm in state 3, there's a selfloop back to state 3.

Now, I've filled out almost all of this deterministic equivalent.

But I forgot to label an edge.

Help me out.

As the quiz, what should the label for this edge be

so that this deterministic equivalent and this nondeterministic machine

accept exactly the same language?