English subtitles

← 01-58 Nondet To Det

Get Embed Code
4 Languages

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

  1. Let's do one more bit of practice
  2. converting non-deterministic machines to deterministic ones.
  3. Here I've written a non-deterministic machine.
  4. It has ambiguity.
  5. Right in state 1 there are 2 ways to go on a.
  6. It also has epsilon transitions,
  7. and I'll start making its deterministic equivalent down here.
  8. Well, when we enter the non-deterministic machine,
  9. we could only be in state 1, but after that we could see an a,
  10. and if I see an a I could be in 2, 4,
  11. or I could take the free epsilon transition to 5,
  12. or I could keep going and take the free epsilon transition to 6.
  13. I'll label my new state 2456
  14. because it keeps track of everywhere that I could have my fingers
  15. if I'm simulating this non-deterministic machine.
  16. Now, should this state be an accepting state or not?
  17. Well, remember that a finite state machine accepts if there's any path
  18. to an accepting state, and 6 is one of our accepting states.
  19. Because the original machine could accept a,
  20. a, epsilon, epsilon, win, we want our new machine to also accept a.
  21. A, win.
  22. In my converted world, the state accepts if any of its corresponding
  23. original states also accept.
  24. Let's say that I'm in either 2, 4, 5, or 6 and I see a c.
  25. If I'm in 2 and I see a c, I fall off the world.
  26. If I'm in 4, fall off the world.
  27. 5, I go to 6, looking good.
  28. 6, fall off the world.
  29. Here if I was in 2, 4, 5, or 6 and I see a c,
  30. I end up just in state 6, and that's definitely an accepting state.
  31. Now, there's some other ways to get out of 2, 4, 5, and 6,
  32. and when we do, we might be in states 2 or 3.
  33. Since 3 is an accepting state up there,
  34. 2 or 3 is an accepting state down here.
  35. If I'm in 2 or 3, on a b from 2 I go to 3,
  36. and c I'd fall off the world, so we'd end up in state 3.
  37. If I'm in 2 or 3 and I see a c,
  38. I must really have been in state 3, and I stay in state 3,
  39. so either on b or c we end up in just state 3,
  40. which is also an accepting state.
  41. And if I'm in state 3, there's a self-loop back to state 3.
  42. Now, I've filled out almost all of this deterministic equivalent.
  43. But I forgot to label an edge.
  44. Help me out.
  45. As the quiz, what should the label for this edge be
  46. so that this deterministic equivalent and this non-deterministic machine
  47. accept exactly the same language?