Japanese subtitles

← 01-58 Nondet To Det

dummy description

Get Embed Code
4 Languages

Showing Revision 1 created 10/23/2014 by Udacity.

  1. 非決定性有限状態機械を
  2. 決定性有限状態機械にもう一度変換してみましょう
  3. ここに非決定性有限状態機械を書きました
  4. あいまいさを含んでいます
  5. ステート1からaが入力された時に
    遷移先が2つあります
  6. イプシロン遷移も見られます
  7. この下に決定性有限状態機械を書きましょう
  8. 非決定性有限状態機械では
  9. 開始ステート1からaを入力すると
  10. ステート2かステート4へ遷移することができます
  11. もしくはイプシロンでステート5へも遷移できます
  12. そのままイプシロン遷移を使い
    ステート6への遷移も可能です
  13. よって新しいステートを2456とします
  14. 今指を置いたすべての場所が
  15. 非決定性有限状態機械で行けるステートです
  16. このステートは受理ステートでしょうか?
  17. 非決定性有限状態機械では受理ステートへ行く道が
  18. 1つでもあれば受理してくれます
  19. 元の非決定性有限状態機械ではaのあと
  20. イプシロン、イプシロンと遷移してaを受理します
  21. 決定性有限状態機械でも同じ結果が必要です
  22. 非決定性有限状態機械で対応するステートが
    1つでも受理ステートならば
  23. そのステートは受理ステートとなります
  24. ステート2、4、5もしくは6にいて
    cを入れるとします
  25. ステート2でcを入れるとそこで終了です
  26. ステート4でも同じ結果です
  27. ステート5ではステート6に行けます
  28. ステート6でも終了してしまいます
  29. ステート2、4、5もしくは6にいてcを入れると
  30. 受理ステートであるステート6に遷移します
  31. ステート2、4、5、6からの他の遷移もあります
  32. ステート2、3へ遷移する方法です
  33. 元の非決定性有限状態機械で
    ステート3が受理ステートですので
  34. このステート2、3は受理ステートです
  35. ステート2からbが入力されると
    ステート3に遷移します
  36. ステート3からbだと終了します
  37. ステート2か3でcを入れると
  38. 元の有限状態機械でステート3にいたはずで
    ステート3に戻ってきます
  39. よってbを入れてもcを入れても
    受理ステートである
  40. ステート3にたどり着くのです
  41. ステート3にいたとしたら
    セルフループでステート3に戻ります
  42. これで決定性有限状態機械はほぼ完成ですが
  43. エッジのラベルを忘れていました
  44. 皆さん考えてみてください
  45. この決定性有限状態機械を
  46. 非決定性有限状態機械と同じように作用させるには
  47. エッジのラベルをどうすべきでしょうか?