Japanese subtitles

← 01-57 Nondeterminism

dummy description

Get Embed Code
5 Languages

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

  1. イプシロン遷移とあいまいさを含む
  2. 有限状態機械を使ってきましたね
  3. あいまいさとは同じ入力で違う場所へ行くことです
  4. これらは非決定性有限状態機械と呼ばれています
  5. ここで使われている非決定性という言葉は
  6. 行き先が定かではないととらえ
  7. 一手一手定められた場所にしか行けないのではなく
  8. 行き先を選択できることです
  9. イプシロン遷移がなく
  10. 遷移先の定まった有限状態機械は
    決定性有限状態機械と呼ばれ
  11. 始めから道筋が決まっています
  12. 有限状態機械と入力だけで
  13. 結果はすべて分かります
  14. FSMシミュレータで作業できるのは
  15. 決定性有限状態機械です
  16. 機械の中で正規表現を実装するのに
  17. とても役立ちます
  18. それでは非決定性有限状態機械の例を
    お見せしましょう
  19. 先ほどの問題を使いましょう
  20. ただ入力を1-23に変えます
  21. 現在のステートはどこでしょう?
  22. 開始ステートから始まります
  23. ここに遷移したとして次はハイフンですので
  24. その場合ステート4に遷移しますね
  25. 2で遷移し次がはっきりしません
  26. セルフループで留まることもできますが
  27. イプシロン遷移で戻ることも可能です
  28. ステート2にいることも
    ステート5にいることもできるのです
  29. 1つに答えを絞ることができないので
  30. 非決定的となるのです
  31. 余談になりますが決定性と非決定性という概念は
  32. 哲学の自由意思説に基づいて作られています
  33. 私たちは個人の意思だけで決断できますか?
  34. それともビリヤードのような
    一手ずつ進むゲームのように
  35. 現状の世界の中で
    すでに定められているものでしょうか?
  36. 混乱を招く意見かもしれませんが
  37. 自由意思はただの錯覚だという哲学者もいます
  38. 主観的な経験については役立つ意見ですが
  39. 周りで何が起きていようとも
  40. 私たちには自由な意志があると信じられています
  41. 有限状態機械に対しても
  42. このような考えが見られます
  43. 非決定性有限状態機械の方が
  44. 多くのことができると思われがちですが
  45. 非決定性有限状態機械で起こり得るすべてのことを
  46. 決定性有限状態機械でも起こせます
  47. 今から自由意思を取り除く作業をしたいと思います
  48. いかなる非決定性有限状態機械にも
  49. 同じ文字列を受理する
    決定性有限状態機械が存在し
  50. 同じ文字列を受理します
  51. 非決定性有限状態機械の方が
    決定性有限状態機械に比べて
  52. パワフルということではないのです
  53. より便利に作られているだけです
  54. 実践して説明します
  55. この主張を例にしてみましょう
  56. 正規表現をこのように設定します
  57. これでは2つの文字列しか受理しません
  58. しかし有限状態機械は入り組んだものにしました
  59. たくさんのイプシロン遷移があります
  60. これは非決定的です
  61. aから始まったあとで2つのイプシロン遷移が
  62. 明確に選択肢を表しています
  63. bを入れるかスキップするという選択肢です
  64. 上の方法ではbを入れ進みます
  65. 下の方法ではその行程をスキップします
  66. 最終的にはcが必要です
  67. では今度はこの非決定性有限状態機械
    同じことをする
  68. 決定性有限状態機械を書いてみます
  69. どのように変更すべきでしょうか
  70. このあとにお見せします
  71. イプシロンでステート3へ遷移できます
  72. このイプシロンはステート6へも遷移可能です
  73. もしくはステート4へ遷移も可能ですので
  74. 合計4ヶ所へ遷移できます
  75. 指がたくさん必要です
  76. すべてを新しいステートの名前として記録します
  77. 有限状態機械は最後まで行く道があれば
    受理しますね
  78. そのためbを入れて遷移することができたら
    ステート3にいたことになります
  79. その場合ステート4へ進むことができます
  80. cで遷移できるとするとステート4にいたことになり
  81. ステート5へ遷移することになります
  82. ステート4にいてcが入力されれば
  83. 決定性有限状態機械でも
  84. 上記の非決定性有限状態機械と
    同じ結果が得られるのです
  85. 2つの文字列a、b、cとa、cはありますが
  86. イプシロン遷移とあいまいさは
  87. 含まれていません
  88. aのラベルを持つエッジは1つしかなく
  89. イプシロン遷移はできません
  90. 他の例を使いどう作用するか見ましょう
  91. もう一度決定性有限状態機械を作ります
  92. この決定性有限状態機械の各ステートは
  93. 非決定性有限状態機械のステートの集合に
  94. 対応するように設定します
  95. 言い換えると非決定性有限状態機械がまず必要で
  96. 同じ言語を受理する
    決定性有限状態機械Dを作ります
  97. 文字列を受理し
  98. 決定性有限機械Dの各ステートを与えられた
  99. 非決定性有限機械のステートの集合に対応させます