Return to Video

01-57 Nondeterminism

  • 0:00 - 0:04
    イプシロン遷移とあいまいさを含む
  • 0:04 - 0:07
    有限状態機械を使ってきましたね
  • 0:07 - 0:11
    あいまいさとは同じ入力で違う場所へ行くことです
  • 0:11 - 0:16
    これらは非決定性有限状態機械と呼ばれています
  • 0:16 - 0:19
    ここで使われている非決定性という言葉は
  • 0:19 - 0:21
    行き先が定かではないととらえ
  • 0:21 - 0:24
    一手一手定められた場所にしか行けないのではなく
  • 0:24 - 0:26
    行き先を選択できることです
  • 0:26 - 0:29
    イプシロン遷移がなく
  • 0:29 - 0:34
    遷移先の定まった有限状態機械は
    決定性有限状態機械と呼ばれ
  • 0:34 - 0:36
    始めから道筋が決まっています
  • 0:36 - 0:38
    有限状態機械と入力だけで
  • 0:38 - 0:40
    結果はすべて分かります
  • 0:40 - 0:43
    FSMシミュレータで作業できるのは
  • 0:43 - 0:46
    決定性有限状態機械です
  • 0:46 - 0:49
    機械の中で正規表現を実装するのに
  • 0:49 - 0:51
    とても役立ちます
  • 0:51 - 0:55
    それでは非決定性有限状態機械の例を
    お見せしましょう
  • 0:55 - 0:57
    先ほどの問題を使いましょう
  • 0:57 - 1:00
    ただ入力を1-23に変えます
  • 1:00 - 1:02
    現在のステートはどこでしょう?
  • 1:02 - 1:05
    開始ステートから始まります
  • 1:05 - 1:08
    ここに遷移したとして次はハイフンですので
  • 1:08 - 1:11
    その場合ステート4に遷移しますね
  • 1:11 - 1:14
    2で遷移し次がはっきりしません
  • 1:14 - 1:17
    セルフループで留まることもできますが
  • 1:17 - 1:20
    イプシロン遷移で戻ることも可能です
  • 1:20 - 1:25
    ステート2にいることも
    ステート5にいることもできるのです
  • 1:25 - 1:28
    1つに答えを絞ることができないので
  • 1:28 - 1:30
    非決定的となるのです
  • 1:30 - 1:34
    余談になりますが決定性と非決定性という概念は
  • 1:34 - 1:39
    哲学の自由意思説に基づいて作られています
  • 1:39 - 1:42
    私たちは個人の意思だけで決断できますか?
  • 1:42 - 1:45
    それともビリヤードのような
    一手ずつ進むゲームのように
  • 1:45 - 1:51
    現状の世界の中で
    すでに定められているものでしょうか?
  • 1:51 - 1:53
    混乱を招く意見かもしれませんが
  • 1:53 - 1:57
    自由意思はただの錯覚だという哲学者もいます
  • 1:57 - 2:00
    主観的な経験については役立つ意見ですが
  • 2:00 - 2:02
    周りで何が起きていようとも
  • 2:02 - 2:05
    私たちには自由な意志があると信じられています
  • 2:05 - 2:07
    有限状態機械に対しても
  • 2:07 - 2:09
    このような考えが見られます
  • 2:09 - 2:12
    非決定性有限状態機械の方が
  • 2:12 - 2:14
    多くのことができると思われがちですが
  • 2:14 - 2:17
    非決定性有限状態機械で起こり得るすべてのことを
  • 2:17 - 2:19
    決定性有限状態機械でも起こせます
  • 2:19 - 2:23
    今から自由意思を取り除く作業をしたいと思います
  • 2:23 - 2:26
    いかなる非決定性有限状態機械にも
  • 2:26 - 2:29
    同じ文字列を受理する
    決定性有限状態機械が存在し
  • 2:29 - 2:33
    同じ文字列を受理します
  • 2:33 - 2:37
    非決定性有限状態機械の方が
    決定性有限状態機械に比べて
  • 2:37 - 2:39
    パワフルということではないのです
  • 2:39 - 2:42
    より便利に作られているだけです
  • 2:42 - 2:44
    実践して説明します
  • 2:44 - 2:46
    この主張を例にしてみましょう
  • 2:46 - 2:48
    正規表現をこのように設定します
  • 2:48 - 2:51
    これでは2つの文字列しか受理しません
  • 2:51 - 2:55
    しかし有限状態機械は入り組んだものにしました
  • 2:55 - 2:57
    たくさんのイプシロン遷移があります
  • 2:57 - 3:00
    これは非決定的です
  • 3:00 - 3:03
    aから始まったあとで2つのイプシロン遷移が
  • 3:03 - 3:05
    明確に選択肢を表しています
  • 3:05 - 3:08
    bを入れるかスキップするという選択肢です
  • 3:08 - 3:10
    上の方法ではbを入れ進みます
  • 3:10 - 3:13
    下の方法ではその行程をスキップします
  • 3:13 - 3:15
    最終的にはcが必要です
  • 3:15 - 3:19
    では今度はこの非決定性有限状態機械
    同じことをする
  • 3:19 - 3:22
    決定性有限状態機械を書いてみます
  • 3:22 - 3:24
    どのように変更すべきでしょうか
  • 3:24 - 3:26
    このあとにお見せします
  • 3:26 - 3:31
    イプシロンでステート3へ遷移できます
  • 3:31 - 3:33
    このイプシロンはステート6へも遷移可能です
  • 3:33 - 3:36
    もしくはステート4へ遷移も可能ですので
  • 3:36 - 3:38
    合計4ヶ所へ遷移できます
  • 3:38 - 3:40
    指がたくさん必要です
  • 3:40 - 3:44
    すべてを新しいステートの名前として記録します
  • 3:44 - 3:49
    有限状態機械は最後まで行く道があれば
    受理しますね
  • 3:49 - 3:54
    そのためbを入れて遷移することができたら
    ステート3にいたことになります
  • 3:54 - 3:57
    その場合ステート4へ進むことができます
  • 3:57 - 4:03
    cで遷移できるとするとステート4にいたことになり
  • 4:03 - 4:06
    ステート5へ遷移することになります
  • 4:06 - 4:10
    ステート4にいてcが入力されれば
  • 4:10 - 4:13
    決定性有限状態機械でも
  • 4:13 - 4:17
    上記の非決定性有限状態機械と
    同じ結果が得られるのです
  • 4:17 - 4:20
    2つの文字列a、b、cとa、cはありますが
  • 4:20 - 4:23
    イプシロン遷移とあいまいさは
  • 4:23 - 4:25
    含まれていません
  • 4:25 - 4:29
    aのラベルを持つエッジは1つしかなく
  • 4:29 - 4:31
    イプシロン遷移はできません
  • 4:31 - 4:34
    他の例を使いどう作用するか見ましょう
  • 4:34 - 4:37
    もう一度決定性有限状態機械を作ります
  • 4:37 - 4:40
    この決定性有限状態機械の各ステートは
  • 4:40 - 4:44
    非決定性有限状態機械のステートの集合に
  • 4:44 - 4:46
    対応するように設定します
  • 4:46 - 4:50
    言い換えると非決定性有限状態機械がまず必要で
  • 4:50 - 4:53
    同じ言語を受理する
    決定性有限状態機械Dを作ります
  • 4:53 - 4:57
    文字列を受理し
  • 4:57 - 5:01
    決定性有限機械Dの各ステートを与えられた
  • 5:01 - 600:00
    非決定性有限機械のステートの集合に対応させます
Cím:
01-57 Nondeterminism
Leírás:

dummy description

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS262 - Programming Languages
Duration:
05:05

Japanese subtitles

Felülvizsgálatok