## ← 01-59 Nondet To Det Solution

• 1 Follower
• 32 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=Nt4oPX7X1QE" data-team="udacity"></div> ``` 4 Languages

Showing Revision 1 created 04/24/2012 by Amara Bot.

1. Well, let's make ourselves a little scratch room and work it out.
2. There are only 1, 2, 3 letters, a, b, and c involved,
3. so let's take a look at each one by one, see if it fits.
4. Suppose I was in state 2456 and I saw an a.
5. If I'm in 2 and I see an a I die, 4 and I see an a I die,
6. 5 and I see an a I die, 6 and I see an a I die.
7. That's not good.
8. 2456 on a goes to failure.
9. It does not go to 23.
10. All right, well, what if I see a b?
11. If I'm in 2 and I see a b, I go to 3. That looks pretty good.
12. 4 and I see a b I die.
13. 5 and I see a b I go to 2.
14. 6 and I see a b I die.
15. Oh, b took us to exactly 2 and 3.
16. 2456 on b went to 2 and 3.
17. But let's just finish checking up on c just in case we missed something.
18. I'm in 2456.
19. 2 on a c goes nowhere.
20. 4 on a c goes nowhere.
21. 5 on a c goes to 6,
22. and 6 on a c goes nowhere, so 2456
23. on a c goes to 6.
24. Actually, we already have that edge, 2456 on a c goes to 6,
25. and since this machine is deterministic, we only want 1
26. outgoing edge here labeled c.
27. It looks like b was our winner.
28. The label for this edge is b.
29. Now, this is not a proof,
30. but it just so happens that any non-deterministic machine
31. can be converted to a deterministic machine
32. using exactly the same steps.