English subtitles

← 01-59 Nondet To Det Solution

Get Embed Code
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.