Return to Video

01-58 Nondet To Det

  • 0:00 - 0:02
    非決定性有限状態機械を
  • 0:02 - 0:06
    決定性有限状態機械にもう一度変換してみましょう
  • 0:06 - 0:09
    ここに非決定性有限状態機械を書きました
  • 0:09 - 0:11
    あいまいさを含んでいます
  • 0:11 - 0:14
    ステート1からaが入力された時に
    遷移先が2つあります
  • 0:14 - 0:16
    イプシロン遷移も見られます
  • 0:16 - 0:20
    この下に決定性有限状態機械を書きましょう
  • 0:20 - 0:23
    非決定性有限状態機械では
  • 0:23 - 0:27
    開始ステート1からaを入力すると
  • 0:27 - 0:31
    ステート2かステート4へ遷移することができます
  • 0:31 - 0:34
    もしくはイプシロンでステート5へも遷移できます
  • 0:34 - 0:38
    そのままイプシロン遷移を使い
    ステート6への遷移も可能です
  • 0:38 - 0:40
    よって新しいステートを2456とします
  • 0:40 - 0:42
    今指を置いたすべての場所が
  • 0:42 - 0:45
    非決定性有限状態機械で行けるステートです
  • 0:45 - 0:48
    このステートは受理ステートでしょうか?
  • 0:48 - 0:52
    非決定性有限状態機械では受理ステートへ行く道が
  • 0:52 - 0:56
    1つでもあれば受理してくれます
  • 0:56 - 0:59
    元の非決定性有限状態機械ではaのあと
  • 0:59 - 1:03
    イプシロン、イプシロンと遷移してaを受理します
  • 1:03 - 1:05
    決定性有限状態機械でも同じ結果が必要です
  • 1:05 - 1:10
    非決定性有限状態機械で対応するステートが
    1つでも受理ステートならば
  • 1:10 - 1:13
    そのステートは受理ステートとなります
  • 1:13 - 1:17
    ステート2、4、5もしくは6にいて
    cを入れるとします
  • 1:17 - 1:20
    ステート2でcを入れるとそこで終了です
  • 1:20 - 1:22
    ステート4でも同じ結果です
  • 1:22 - 1:24
    ステート5ではステート6に行けます
  • 1:24 - 1:27
    ステート6でも終了してしまいます
  • 1:27 - 1:31
    ステート2、4、5もしくは6にいてcを入れると
  • 1:31 - 1:36
    受理ステートであるステート6に遷移します
  • 1:36 - 1:39
    ステート2、4、5、6からの他の遷移もあります
  • 1:39 - 1:42
    ステート2、3へ遷移する方法です
  • 1:42 - 1:45
    元の非決定性有限状態機械で
    ステート3が受理ステートですので
  • 1:45 - 1:48
    このステート2、3は受理ステートです
  • 1:48 - 1:52
    ステート2からbが入力されると
    ステート3に遷移します
  • 1:52 - 1:57
    ステート3からbだと終了します
  • 1:57 - 1:59
    ステート2か3でcを入れると
  • 1:59 - 2:02
    元の有限状態機械でステート3にいたはずで
    ステート3に戻ってきます
  • 2:02 - 2:07
    よってbを入れてもcを入れても
    受理ステートである
  • 2:07 - 2:09
    ステート3にたどり着くのです
  • 2:09 - 2:13
    ステート3にいたとしたら
    セルフループでステート3に戻ります
  • 2:13 - 2:17
    これで決定性有限状態機械はほぼ完成ですが
  • 2:17 - 2:20
    エッジのラベルを忘れていました
  • 2:20 - 2:22
    皆さん考えてみてください
  • 2:22 - 2:24
    この決定性有限状態機械を
  • 2:24 - 2:28
    非決定性有限状態機械と同じように作用させるには
  • 2:28 - 600:00
    エッジのラベルをどうすべきでしょうか?
Title:
01-58 Nondet To Det
Description:

dummy description

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
02:32

Japanese subtitles

Revisions