Zenn
Closed9

100日チャレンジ day30 (有限オートマン可視化ツール)

llmバックエンド100日チャレンジ
riddle_tecriddle_tec

昨日
https://zenn.dev/gin_nazo/scraps/3f7980415e3009

https://blog.framinal.life/entry/2025/04/14/154104

100日チャレンジに感化されたので、アレンジして自分でもやってみます。

やりたいこと

  • 世の中のさまざまなドメインの簡易実装をつくり、バックエンドの実装に慣れる(dbスキーマ設計や、関数の分割、使いやすいインターフェイスの切り方に慣れる
  • 設計力(これはシステムのオーバービューを先に自分で作ってaiに依頼できるようにする
  • 生成aiをつかったバイブコーティングになれる
  • 実際にやったことはzennのスクラップにまとめ、成果はzennのブログにまとめる(アプリ自体の公開は必須ではないかコードはgithubにおく)

できたもの

https://github.com/lirlia/100day_challenge_backend/tree/main/day30_fsm_visualizer

riddle_tecriddle_tec

承知いたしました。ユーザー機能とバックエンドを省略し、フロントエンドのみで完結する「有限オートマトン (State Machine) 可視化ツール」として仕様を修正します。データはブラウザのローカルストレージに保存し、初期表示用にサンプルデータを用意します。

アプリケーション概要 (修正版)

ユーザーが決定性有限オートマトン (DFA) を対話的に定義し、その構造をグラフとして視覚化し、与えられた入力文字列に対する動作をステップごとにシミュレーションできるフロントエンドWebアプリケーションです。定義データはブラウザのローカルストレージに保存され、アプリケーション起動時にはサンプルオートマトンが表示されます。

主要機能

  1. オートマトン定義:
    • 状態 (States): 追加・削除・ラベル編集。
    • アルファベット (Alphabet): 定義・編集。
    • 遷移関数 (Transitions): ある状態から特定の入力文字による遷移先状態を定義・編集・削除。
    • 開始状態 (Start State): 状態の中から1つ指定。
    • 受理状態 (Accept States): 状態の中から複数指定。
  2. オートマトン可視化:
    • React Flow を使用し、定義されたオートマトンをリアルタイムにグラフ表示（ノード: 状態、エッジ: 遷移）。
    • 開始状態（入口矢印など）、受理状態（二重円など）を区別して表示。
    • ノードはドラッグ可能。
  3. 実行シミュレーション:
    • 入力文字列を与え、ステップ実行または一括実行。
    • シミュレーション中は現在の状態ノードと適用される遷移エッジをハイライト表示。
    • 最終的な受理 (Accepted) / 拒否 (Rejected) 結果を表示。
  4. オートマトンの永続化と管理:
    • 定義したオートマトンに名前を付けてローカルストレージに保存。
    • 保存したオートマトンを一覧（例: ドロップダウン）から選択して読み込み、編集・シミュレーション可能。
    • オートマトンの削除機能。
    • 初期データ: アプリケーション初回起動時（またはローカルストレージが空の場合）に、サンプルDFA（例: 文字列 "abb" を受理する、アルファベット {a, b} のオートマトン）を自動的にロードして表示。

技術スタック

  • フレームワーク: Next.js (App Router)
  • 言語: TypeScript
  • スタイリング: Tailwind CSS
  • グラフ可視化: React Flow (reactflow)
  • 状態管理: Zustand (UI状態とオートマトン定義を一元管理)
  • 永続化: Browser Local Storage

データ構造 (フロントエンド)

// ローカルストレージに保存する基本単位
interface AutomatonDefinition {
  id: string; // ユニークID (例: cuid() or Date.now().toString())
  name: string; // オートマトンの名前
  alphabet: string[]; // 入力文字の配列 (例: ['a', 'b'])
  states: { id: string; label: string; isAccepting: boolean }[]; // 状態のリスト
  transitions: { id: string; fromStateId: string; toStateId: string; input: string }[]; // 遷移のリスト
  startStateId: string | null; // 開始状態のID
  // React Flow 用のレイアウト情報 (オプションだが推奨)
  layout?: {
    nodes: { id: string; position: { x: number; y: number } }[];
    // edges: { id: string; /* 必要ならエッジのレイアウト情報 */ }[];
  };
}

// React Flow が直接扱うノード/エッジの型 (上記 Definition から変換)
// (React Flow の Node, Edge 型をインポートして利用)
// import type { Node, Edge } from 'reactflow';

// Zustand ストアの状態 (例)
interface AutomatonStore {
  automata: { [id: string]: AutomatonDefinition }; // ローカルストレージから読み込んだ全オートマトン
  activeAutomatonId: string | null; // 現在編集中のオートマトンID
  // React Flow用のノードとエッジ (activeAutomatonId に基づき生成)
  nodes: Node[];
  edges: Edge[];
  // UI操作やシミュレーションに関する状態
  // ... (例: シミュレーション中の状態ID、入力文字列など)

  // アクション (メソッド)
  loadAutomata: () => void; // ローカルストレージから読み込み
  saveAutomaton: (definition: AutomatonDefinition) => void; // 保存
  deleteAutomaton: (id: string) => void; // 削除
  setActiveAutomaton: (id: string) => void; // アクティブなものを設定
  updateActiveAutomaton: (updates: Partial<AutomatonDefinition>) => void; // 変更を反映
  generateFlowElements: () => void; // DefinitionからNodes/Edgesを生成
  // ... 他のアクション
}

実装の順序 (修正版)

  1. プロジェクト初期化:
    • template を day30_fsm_visualizer にコピー。
    • cd day30_fsm_visualizer を実行。
    • package.json の name を day30_fsm_visualizer に変更。
    • npm install reactflow zustand @reactflow/node-resizer @reactflow/node-toolbar を実行。
    • README.md を作成し、今回のアプリ概要を記載。
  2. 基本レイアウトと状態管理設定:
    • app/page.tsx (または適切なページパス) に基本的なUI構造（ヘッダー、メイン領域）を作成。
    • Zustand ストア (lib/store.ts など) をセットアップ。ローカルストレージの読み書きロジック、サンプルデータ定義を含む。
  3. React Flow 初期表示:
    • ストアから取得したサンプルデータ（またはローカルストレージのデータ）を React Flow が要求する nodes と edges の形式に変換。
    • ReactFlowProvider でラップし、<ReactFlow nodes={...} edges={...} ... /> コンポーネントでグラフを表示。
    • 開始状態、受理状態のスタイルを適用（カスタムノード or スタイル）。
  4. オートマトン定義UI:
    • オートマトン名、アルファベット、状態リスト、遷移リストを編集するためのフォームコンポーネント群を作成。
    • 状態追加/削除、遷移追加/削除ボタンとロジック。
    • 状態をクリックして開始/受理状態を切り替える機能。
    • これらの変更が Zustand ストアに反映され、React Flow の表示がリアルタイムに更新されるようにする。
  5. ローカルストレージ連携:
    • オートマトン一覧（ドロップダウンなど）と新規作成/保存/削除ボタンを実装。
    • Zustand ストアのアクションを呼び出し、ローカルストレージとの同期を行う。
  6. シミュレーション機能:
    • 入力文字列フィールド、実行/ステップ実行/リセットボタンを配置。
    • シミュレーションロジック（現在の状態、次の入力、遷移先特定、受理/拒否判定）を実装。
    • シミュレーションの進行に合わせて Zustand ストアの状態を更新し、React Flow のノード/エッジのハイライト（animated や className の変更）を行う。
    • 結果表示エリアを設ける。
  7. 仕上げとテスト:
    • ブルータリズムのデザインテーマを適用。
    • 一連の操作（定義、保存、読込、シミュレーション）が意図通り動作するか確認。
    • 不要なコードやファイルを削除。
    • (オプション) Playwright などで簡単な E2E テストを作成。
  8. ドキュメント更新:
    • README.md に使い方や機能を追記。
    • .cursor/rules/knowledge.mdc に今回のアプリ情報を追加。

この修正版仕様と実装計画で進めます。まずはプロジェクトの初期設定から開始します。

riddle_tecriddle_tec

スクリーンショットありがとうございます！初期表示は期待通りですね 👍

では、次に基本的な操作としてシミュレーションを試してみましょう。

  1. 右側の「Simulation」パネルを見てください。
  2. 一番上の**「Input String」**というテキストボックスに、abb と入力してください。
  3. すぐ下にある**「Run」**ボタンをクリックしてください。

これを実行すると、中央のグラフのノードとエッジが順番に緑色にハイライトされ、最終的に右パネルの「Status」セクションの「Result」が Accepted (緑色の文字) になるはずです。

素晴らしい！シミュレーションの基本動作は問題なさそうですね。

では、次に拒否されるケースを試してみましょう。

  1. まず、右パネルの「Controls」セクションにある**「Reset」**ボタンをクリックしてください。これでシミュレーションの状態がリセットされます（Result が Idle に戻るはずです）。
  2. 次に、「Input String」に ab と入力してください。
  3. 再度**「Run」**ボタンをクリックしてください。

今度は、グラフのハイライトが q0 → q1 → q2 と進んだところで止まり、右パネルの「Result」が Rejected (赤色の文字) になるはずです。

いかがでしょうか？

完璧です！受理と拒否のシミュレーションが正しく動作することを確認できました。

次はステップ実行を試してみましょう。

  1. 再度**「Reset」**ボタンをクリックしてください。
  2. 「Input String」に a と入力してください。
  3. 「Controls」セクションの**「Step」ボタンを1回だけ**クリックしてください。
  • グラフでは q0 から q1 への遷移 (a のエッジ) と q1 ノードがハイライトされます。
  • 右パネルの「Status」では、Result が Running、Current State が q1 (または q1 のラベル)、Step が 1 になるはずです。
  1. もう一度**「Step」**ボタンをクリックしてください。
  • 入力 a を処理しきったので、シミュレーションは終了します。
  • q1 は受理状態ではないため、Result が Rejected になるはずです。ハイライトは解除されます。

このステップ実行の挙動も確認してみてください。

定義変更も問題なく反映されるようですね！

続いて、状態と遷移の追加・削除をテストしましょう。

1. 状態の追加と削除:

  • 左パネルの「States」セクションの一番下にある**「New state label」**テキストボックスに q_new と入力してください。
  • その隣の**「Add State」**ボタンをクリックしてください。
  • 中央のグラフに q_new というラベルの新しいノードが追加されるはずです（位置はランダムなので、他のノードと重なっているかもしれません）。
  • 追加された q_new の行にある、赤い背景の**「X」**ボタン (Delete State) をクリックしてください。
  • グラフから q_new ノードが削除されるはずです。

2. 遷移の追加と削除:

  • まず、DFA制約により失敗するケースを試します。左パネルの「Transitions」セクションの一番下を見てください。
    • 「From」ドロップダウンで start (旧q0) を選択。
    • 「Input」ドロップダウンで a を選択。
    • 「To」ドロップダウンで trap を選択。
    • **「Add Transition」**ボタンをクリックします。既に start --(a)--> q1 という遷移があるため、この遷移は追加できないはずです。ブラウザの開発者コンソールに DFA Violation:... という警告メッセージが出力されるか、あるいはボタンが無効化されるなどの挙動を確認してください。（現状ではコンソールへの警告のみ実装しています）
  • 次に、成功するケースを試します。
    • 「From」: start
    • 「Input」: b
    • 「To」: q1
    • **「Add Transition」**ボタンをクリックしてください。
    • グラフに start から q1 へ向かう b ラベルの新しい矢印（エッジ）が追加されるはずです。
  • 最後に、削除を試します。
    • 左パネルの「Transitions」リストに追加された start --(b)--> q1 の行にある、赤い背景の**「X」**ボタンをクリックしてください。
    • グラフから対応する矢印が削除されるはずです。

これらの追加・削除操作を試してみてください。

状態と遷移の追加・削除も確認できたようですね。素晴らしいです。

最後に、**オートマトン自体の管理機能（新規作成、切り替え、削除）**をテストしましょう。

1. 新規オートマトンの作成:

  • 左パネルの一番上にある、オートマトン選択ドロップダウンの下の**「New」**ボタンをクリックしてください。
  • グラフと定義フォームの内容がクリアされ、オートマトン名が "New Automaton" になることを確認してください。
  • Alphabet が "a, b" になっていることも確認します。

2. 新規オートマトンでの簡単な定義とテスト:

  • この新しいオートマトンで、以下の簡単な定義をしてみましょう。
    • 「States」で "S0" と "S1" を追加。
    • "S0" の行の「S」ボタンをクリックして開始状態に設定。
    • "S1" の行の「A」ボタンをクリックして受理状態に設定。
    • 「Transitions」で From: S0, Input: a, To: S1 の遷移を追加。
  • 定義できたら、右パネルでシミュレーションを試します。
    • Input String に a と入力し「Run」→ Accepted になるはずです。
    • 「Reset」して Input String に b と入力し「Run」→ Rejected になるはずです。

3. オートマトンの切り替えと削除:

  • 左パネル一番上のドロップダウンをクリックし、"Sample DFA (accepts "abb")" を選択してください。
    • 最初のサンプルオートマトンのグラフと定義が再表示されるはずです。
  • 再度ドロップダウンで "New Automaton" を選択してください。
  • **「Delete」**ボタンをクリックしてください。確認ダイアログが表示されるので「OK」をクリックします。
  • "New Automaton" が削除され、自動的に "Sample DFA (...)" が選択された状態に戻るはずです。
  • この時点でオートマトンが1つしかないので、「Delete」ボタンが無効化（クリックできない状態）になっていることも確認してください。

これらの操作を一通り試してみてください。

riddle_tecriddle_tec

有限オートマトン（Finite Automaton、FA）または有限状態機械（Finite State Machine、FSM）は、計算理論における非常に基本的な計算モデルの一つです。簡単に言うと、「限られた数の状態」と「状態間の遷移ルール」を持つ機械のようなものです。

主な特徴と構成要素は以下の通りです。

  1. 状態 (States): 機械が取りうる状況や段階のことです。例えば、信号機なら「赤」「黄」「青」が状態にあたります。今回作成したツールでは、グラフの丸いノード (q0, q1, ...) がこれに相当します。
  2. 入力記号 / アルファベット (Input Symbols / Alphabet): 機械が受け付けることができる文字や記号の集まりです。例えば、特定の文字列をチェックするなら a や b、数字なら 0 や 1 などです。
  3. 遷移関数 (Transition Function): 「現在の状態」で「特定の入力記号」を受け取ったときに、「次にどの状態へ移るか」を定義したルールです。グラフの矢印（エッジ）がこれにあたり、矢印にはどの入力記号で遷移するかが書かれています。
  4. 開始状態 (Start State): 機械が動作を開始するときの最初の状態です。グラフでは特別な印（今回は緑枠）が付いています。
  5. 受理状態 (Accept State(s)): 機械が特定の入力文字列を処理し終わったときに、もしこの状態にいれば、その入力文字列は「受理された（認識された）」とみなされる状態のことです。複数存在することもあります。グラフでは二重円で表現しました。

動作の仕組み:

有限オートマトンは、開始状態からスタートし、与えられた入力文字列を先頭から一文字ずつ読み込みます。そして、現在の状態と読み込んだ入力記号に基づいて、遷移関数に従って次の状態へ移ります。入力文字列を最後まで読み込んだ時点で、機械が受理状態にいれば、その入力文字列は「受理された」ことになります。そうでなければ「拒否された」ことになります。

何に使われるか？

非常に単純なモデルですが、以下のような様々な場面で基礎として使われています。

  • パターンマッチング: テキストの中から特定の単語や形式（メールアドレス、URLなど）を見つける正規表現エンジンの内部など。
  • コンパイラの字句解析: プログラムコードを読み込み、キーワード、識別子、演算子などの意味のある単位（トークン）に分割する処理。
  • 単純な制御システム: 自動販売機、信号機、エレベーターなど、状態が明確に分かれているシステムの動作制御。
  • プロトコル設計: 通信プロトコルにおける状態遷移の定義。
  • 今回作成したツール: まさに、この有限オートマトンの定義と動作を視覚的に理解するためのものです。

要するに、「決まったルールに従って状態が変わっていき、最終的な状態で何かを判断する」 という仕組みをモデル化したもの、と考えると分かりやすいかもしれません。

riddle_tecriddle_tec

有限オートマンをそのまま使うというより、ステートを管理する際にはこの思想が使われるということ？

はい、その理解でほぼ正しいです。

  • 厳密な「有限オートマトン」（今回作ったツールで扱うような、数学的に定義されたモデル）をそのままの形でソフトウェアに組み込むことは、特定の分野（例: 正規表現エンジン、コンパイラの字句解析器、一部の形式検証）以外では比較的まれです。

  • しかし、「状態（State）」と「遷移（Transition）」という考え方（思想）、つまり**「ステートマシン」の概念は、ソフトウェア開発において非常に広く、頻繁に利用**されています。

多くのシステムやコンポーネントは、内部的に何らかの状態を持っており、イベントや入力に応じてその状態が変化します。この「状態と遷移」を明確に意識して設計・実装することで、以下のようなメリットがあります。

  1. 複雑さの管理: システムの振る舞いを、取りうる状態とその間の遷移として整理することで、複雑なロジックを理解しやすく、管理しやすくなります。
  2. バグの削減: 不正な状態遷移や、想定外の状態で処理が行われることを防ぎやすくなります。例えば、「ログインしていない」状態では「ログアウト」ボタンは押せない、といった制御が明確になります。
  3. 見通しの良さ: コードが「今どういう状態で、何が起きたら次にどうなるか」という観点で記述されるため、他の開発者が理解しやすくなります。
  4. テスト容易性: 各状態や遷移を個別にテストしやすくなります。

例:

  • UIコンポーネントの状態（loading, loaded, error など）
  • ユーザー認証の状態（guest, authenticating, authenticated など）
  • ゲームキャラクターの状態（idle, walking, attacking, jumping など）
  • 非同期処理の状態（pending, fulfilled, rejected など）
  • 複雑なワークフロー（注文処理: new, processing, shipped, delivered, cancelled など - Day15のクレジットカード申請もこれに近い）

このように、私たちが「有限オートマトン可視化ツール」で作ったような厳密な定義（アルファベット、受理状態など）は常に必要ではありませんが、その根底にある**「システムの状態を明確に定義し、状態間の遷移ルールを管理する」**という考え方は、ソフトウェア工学における重要な設計原則の一つと言えます。

今回ツールを作ったことで、この「ステートマシン」という考え方の基礎を視覚的に理解できたのではないでしょうか。

「有限オートマトン」の「有限（Finite）」という言葉は、主に以下の2つの要素が**限られている（無限ではない）**ことを指しています。

  1. 状態の数が有限 (Finite number of states):

    • これが最も重要な意味です。オートマトンが取りうる「状態」（例: q0, q1, start, error など）の数が、無限ではなく、あらかじめ決められた有限個であることを意味します。
    • 例えば、信号機は「赤」「黄」「青」の3つの状態しかありません。無限に新しい状態が増えることはありません。
    • これに対して、例えば「スタック（データを積み重ねる構造）を持つオートマトン」や「チューリングマシン」といった、より強力な計算モデルでは、実質的に無限の状態を持つことができます（スタックの内容やテープの内容によって状態が無数に考えられるため）。

  2. メモリ（記憶容量）が有限 (Finite memory):

    • これは(1)と密接に関連しますが、有限オートマトンは基本的に**「現在の状態」しか覚えていません**。過去にどのような状態を経てきたか、入力文字列のどの部分を読み込んだか、といった情報を（状態そのもの以外で）追加的に記憶するためのメモリは持っていません（あるいは非常に限られています）。
    • 遷移に必要な情報は「現在の状態」と「今読み込んだ入力記号」だけです。入力文字列全体をどこかに保存しておいて後で見返す、といったことはできません。

この「有限性」があるために、有限オートマトンができることには限界があります。例えば、「入力された 0 の数と 1 の数が同じ文字列（例: 0011, 0101）」を正確に認識することはできません。なぜなら、0 がいくつ来たかを数え続けるには、無限の記憶容量（状態）が必要になる可能性があるからです。

しかし、この単純さ・有限さゆえに、その動作を解析したり、効率的に実装したりすることが容易であるという利点もあります。

このスクラップは4ヶ月前にクローズされました