visual-learning
計算機構と言語処理 インタラクティブ可視化
オートマトン・正規表現・構文解析・チューリングマシンなど「計算とは何か」を 1 ステップずつ動かして学ぶ。
visual-learning シリーズ：全分野は シリーズ一覧 からたどれます。
POC 一覧
計算機構と言語処理
有限オートマトン：状態を渡り歩く
状態グラフ（ノード/辺）に入力を1文字ずつ食わせ、現在状態が光って移動→受理/拒否が決まる
開く →
計算機構と言語処理操車場アルゴリズム：中置→逆ポーランド
中置式をスタックと出力キューで逆ポーランドへ1ステップ変換
開く →
計算機構と言語処理構文木を評価する：葉から値が登る
式の抽象構文木で葉のリテラルから値を計算して根へ集約
開く →
計算機構と言語処理正規表現の暴走：破滅的バックトラック
(a+)+のような式に長い文字列を食わせるとマッチ試行が指数爆発する様子を試行ツリーと試行回…
開く →
計算機構と言語処理正規表現→NFA：式から機械が生える
正規表現を入力するとトンプソン構成で NFA が組み上がる
開く →
計算機構と言語処理文脈自由文法：構文木が育つ
文法規則から文字列を導出→構文木が枝分かれして育つ
開く →
計算機構と言語処理再帰下降構文解析：規則を降りていく
式を入力すると expr→term→factor を再帰的に降りて構文木を組む過程を、コール…
開く →
計算機構と言語処理チューリングマシン：テープを書き換える
テープ・ヘッド・状態表をステップ実行
開く →