Open10
Finite State Machines and Algorithmic State Machinesを読む
ytaisei（たいせー）
| 項目 | FSM | ASM |
|---|---|---|
| 基本概念 | 状態と遷移のみ | 状態、遷移、動作を組み合わせて表現 |
| 表記方法 | 状態遷移図、状態遷移表 | ASMチャート |
| 処理の記述 | 単純な状態遷移の定義 | 具体的な処理（演算や条件分岐）を含む |
| 用途 | 制御システム、通信プロトコル | マイクロプロセッサ、デジタル回路設計 |
| 柔軟性 | 限られた遷移制御のみ | 複雑なアルゴリズムの表現が可能 |
ytaisei（たいせー）Abstract Automata
オートマトンは、入力に基づいて状態を遷移し、出力を生成。状態、入力、出力、遷移関数、出力関数の5つの要素から構成され、入力に応じて状態を遷移しながら出力を生成する。
Mealy Automaton
Mealyオートマトンは、入力に基づいて出力を生成する。
- 頂点（Vertex）
- 各頂点はオートマトンの状態を表します。例えば、状態 ( a_m ) や状態 ( a_s ) などが頂点として描かれます。
- アーク（Arc）
- アークは、ある状態から別の状態への遷移を示します。例えば、状態 ( a_m ) から状態 ( a_s ) への遷移がある場合、状態図には ( a_m ) から ( a_s ) への矢印が描かれます。
Mealyオートマトンの特徴は、出力が遷移に依存することです。つまり、入力が与えられたときに、状態が変わると同時に出力も生成されます。
これは、状態が変わるタイミングで出力が即座に決定されるため、応答が速いという利点があります。
Moore Automaton
Mooreオートマトンは、状態に基づいて出力を生成する
| 特徴 | Mealyオートマトン | Mooreオートマトン |
|---|---|---|
| 出力の生成 | 入力と現在の状態に基づいて出力が生成される。 | 現在の状態に基づいて出力が生成される。 |
| 出力のタイミング | 入力が変わると即座に出力が変わる。 | 状態が変わるまで出力は変わらない。 |
| 出力の依存関係 | 出力は入力に依存する。 | 出力は状態に依存する。 |
| 状態遷移の表現 | 遷移の矢印に出力が記載される。 | 各状態に出力が記載される。 |
| 設計の複雑さ | 入力に応じた出力の設計が必要で、やや複雑。 | 状態に基づく出力の設計が簡単。 |
| 応答速度 | 入力に対する応答が速い。 | 状態遷移後に出力が変わるため、応答が遅れることがある。 |
| 例 | 状態 ( a ) から状態 ( b ) への遷移が、入力 ( z ) によって引き起こされ、出力 ( w ) が生成される。 | 状態 ( a ) にいるときは常に出力 ( w_1 ) が生成され、状態 ( b ) に遷移すると出力 ( w_2 ) に変わる。 |
ytaisei（たいせー）オートマトンの完全性
Mealyオートマトンが「完全」または「完全に指定された」と呼ばれるのは、すべての状態 ( a_m ) と入力 ( z_f ) の組み合わせに対して、遷移関数 ( \delta ) と出力関数 ( \lambda ) が定義されている場合
Mooreオートマトンが「完全」または「完全に指定された」と呼ばれるのは、すべての状態 ( a_m ) と入力 ( z_f ) の組み合わせに対して、遷移関数 ( \delta ) が定義されており、さらにすべての状態 ( a_m ) に対して出力関数 ( \lambda ) が定義されている場合
Mealyオートマトンの実際の例
不完全になるケース
- 現在の状態と入力に基づく出力が指定されていない。
- 現在の状態と入力に基づく状態遷移が指定されていない。
ytaisei（たいせー）Mealyオートマトンの実際の例
不完全になるケース
- 現在の状態と入力に基づく出力が指定されていない。
- 現在の状態と入力に基づく状態遷移が指定されていない。
ytaisei（たいせー）
ざっくり、Mooreの方がMealyよりも直感的に構築できる一方で、Mealyの方がStateがシンプルになる
ytaisei（たいせー）State minimization
オートマトンS内に同等の状態が存在しない場合最小とされる。
最小化のステップ
- 状態の分割: オートマトンの状態を同じ振る舞いをする状態ごとにグループ（ブロック）に分ける。
- 状態の置き換え: 各グループを1つの状態にまとめる。
ytaisei（たいせー）Algorithmic State Machine
- ASMの頂点は、出力から入力への弧で接続され、各出力は1つの入力にのみ接続される。
- 各入力は少なくとも1つの出力に接続されている。
- 各頂点は「開始」から「終了」までの経路の少なくとも1つに含まれている。
ytaisei（たいせー）これをみる
