0:00:00.000,0:00:06.000
この問題は少し難しいので[br]2つ星レベルに分類します

0:00:06.000,0:00:10.000
ここでは有限状態機械を最適化していきます

0:00:10.000,0:00:15.000
図のような有限状態機械があったとします

0:00:15.000,0:00:21.000
ステート1には受理状態が1つあり[br]他にもいくつかステートがあります

0:00:21.000,0:00:23.000
図をよく見て考えてください

0:00:23.000,0:00:28.000
bの道を通ってステート2に進めば[br]受理状態には行けません

0:00:28.000,0:00:32.000
ステート2、ステート3またはステート4から[br]ステート1に行く道はなく

0:00:32.000,0:00:36.000
この道を行く文字列はどれも失敗に終わります

0:00:36.000,0:00:40.000
この状態機械はステート1以外を[br]含まないのと同じです

0:00:40.000,0:00:42.000
ならばもっとシンプルにしましょう

0:00:42.000,0:00:44.000
でも何のためにですか？

0:00:44.000,0:00:49.000
Webブラウザを作るために[br]多くの正規表現を使ってきました

0:00:49.000,0:00:55.000
正規表現は有限状態機械として表され[br]そして処理されます

0:00:55.000,0:01:01.000
つまりブラウザの高速化に[br]有限状態機械の小型化は必須なのです

0:01:01.000,0:01:03.000
ではコードを書いていきます

0:01:03.000,0:01:07.000
この有限状態機械の定義を基に考えましょう

0:01:07.000,0:01:11.000
まず実行に関係しないステートを識別し

0:01:11.000,0:01:15.000
それらを死状態として定義から取り除きます

0:01:15.000,0:01:19.000
ただし最適化前に使われていた言語をそのまま保ち

0:01:19.000,0:01:25.000
まったく同じ文字列と一致するようにしたまま[br]取り除く必要があります

0:01:25.000,0:01:28.000
どのように進めるか計画を立てましょう

0:01:28.000,0:01:31.000
これが計画です

0:01:31.000,0:01:37.000
ステップ1では生状態と死状態を探します

0:01:37.000,0:01:41.000
生状態を探しそれ以外は死んでいると推測します

0:01:41.000,0:01:43.000
具体的な方法はこうです

0:01:43.000,0:01:48.000
まずは辞書を反復しすべてのステートを探します

0:01:48.000,0:01:53.000
そしてそれぞれのステートに[br]nfsmacceptsを実行します

0:01:53.000,0:01:55.600
これはレッスン1の宿題に出てきました

0:01:55.600,0:01:59.000
有限状態機械の定義として

0:01:59.000,0:02:06.000
開始ステートと受理状態[br]そして遷移の辞書を受け取り

0:02:06.000,0:02:11.000
あるステートから受理状態に[br]たどりつけるかどうかを見るプロシージャでした

0:02:11.000,0:02:15.000
nfsmacceptsに図の定義とステート3を与えると

0:02:15.000,0:02:20.000
ステート1には行けず[br]つまりどの受理状態にも行けません

0:02:20.000,0:02:22.350
ステート1を与えると成功します

0:02:22.350,0:02:25.000
これを生と死の定義として

0:02:25.000,0:02:30.000
生状態と死状態を見分けていきます　楽しいですね

0:02:30.000,0:02:37.000
ステップ2では死状態を持たない[br]新しい有限状態機械を作ります

0:02:37.000,0:02:43.000
賢くきれいな定義を作るために[br]注意すべきことがあります

0:02:43.000,0:02:46.000
死状態につながる遷移は含めません

0:02:46.000,0:02:49.000
すべての死状態を取り除き

0:02:49.000,0:02:55.000
生状態へとつながらないステートも[br]取り除いていきます

0:02:55.000,0:02:57.000
詳細を確認しましょう

0:02:57.000,0:03:01.000
各エッジのステートと辞書のエントリを見ます

0:03:01.000,0:03:06.000
今のステートが死状態なら[br]新しい有限状態機械にコピーしません

0:03:06.000,0:03:11.000
そうでなければ元の有限状態機械にあった[br]すべての行き先を見て

0:03:11.000,0:03:15.000
生状態のものをすべてコピーする準備をします

0:03:15.000,0:03:20.000
生状態がない場合は[br]そのエッジを取り除きコピーはしません

0:03:20.000,0:03:25.000
図にあるすべてのステートで[br]そのプロセスを繰り返したら

0:03:25.000,0:03:29.000
それに基づき受理状態のリストを更新します

0:03:29.000,0:03:33.000
死んでいる受理状態は必要ありません

0:03:33.000,0:03:35.000
解答を見てみましょう

0:03:35.000,0:03:40.000
まずレッスン1の宿題からnfsmacceptsのコードを

0:03:40.000,0:03:45.000
そっくりそのままコピーしました[br]何も変えていません

0:03:45.000,0:03:49.000
次は有限状態機械のトリミングです

0:03:49.000,0:03:52.000
先ほど説明したようにすべてのステートを探します

0:03:52.000,0:03:55.000
コピーが存在することもあります

0:03:55.000,0:03:59.000
少しトリミングに時間がかかるかもしれませんが

0:03:59.000,0:04:04.000
実行にかかる時間が節約できれば問題ありません

0:04:04.000,0:04:11.000
各ステートが生きているかどうかは[br]nfsmacceptsを実行すれば分かります

0:04:11.000,0:04:14.000
もし生きていたら生状態のリストに加えます

0:04:14.000,0:04:18.000
では新しいエッジの辞書を作成しましょう

0:04:18.000,0:04:24.500
もし古い辞書のエッジの遷移元に生状態があれば

0:04:24.500,0:04:27.000
それを基に更新していきます

0:04:27.000,0:04:34.000
新しい行き先を計算し[br]死んでいる行き先を取り除くわけです

0:04:34.000,0:04:38.000
古いエッジの行き先が生きていたら[br]リストに追加します

0:04:38.000,0:04:44.000
しかし新しい有限状態機械に[br]新しいエッジを設定するのは

0:04:44.000,0:04:48.000
行き先が空でない場合のみです

0:04:48.000,0:04:52.000
どこにも行き着かず失敗するエッジはいりません

0:04:52.000,0:04:56.000
エッジが存在しない場合は失敗すると推測します

0:04:56.000,0:05:02.000
最後に受理状態を生きているものだけとする[br]更新を加えてください

0:05:02.000,0:05:08.000
そして新しいエッジと新しい受理状態の[br]タプルを返します

0:05:08.000,0:05:11.000
これで完了です

0:05:11.000,0:05:15.000
見てください　Trueと出ています

0:05:15.000,0:05:17.000
Trueは真です

0:05:18.000,0:05:23.000
いいですね　すばらしいです