有限オートマトン
仕様及び記述言語(SDL) はITUの標準規格であり、遷移の際の以下のような動作を表す記号を定義している。
イベント送信
イベント受信
タイマ開始
タイマキャンセル
別の並行動作するステートマシンを開始
判断
SDLには、Abstract Data Types と呼ばれる基本データ型、動作言語、有限状態機械を実行可能にするための実行意味論を埋め込む。
デフォルトの形式では全体関数であることを要求するアルゴリズムも存在する。
有限状態機械は制限されたチューリングマシンと見ることもでき、ヘッドが読み取り動作しかできず、常に左から右へと読み取っていくチューリングマシンと言える。
トランスデューサ有限オートマトンは ⟨Σ, Γ, S, s0, δ, ω⟩ の6要素から構成される。
Σ は入力文字セット(有限だが空ではないシンボルの集合)
Γ は出力文字セット(有限だが空ではないシンボルの集合)
S は有限であって空でない状態の集合
s0 は S の要素でもある初期状態(非決定性有限オートマトンの場合は初期状態の集合)
δ は状態遷移関数: δ: S × Σ → S
ω は出力関数
出力関数が状態と入力文字の関数 (ω: S × Σ → Γ ) ならば、その定義はミーリ・モデルであり、ミーリ・マシンとしてモデル化できる。出力関数が状態のみに依存する (ω: S → Γ ) ならば、その定義はムーア・モデルであり、ムーア・マシンとしてモデル化できる。出力機能のない有限オートマトンは状態遷移系などと呼ばれる。
ムーア・マシンの最初の出力シンボル ω ( s 0 ) {\displaystyle \omega (s_{0})} を無視すれば、ミーリ・マシンで遷移ごとに遷移先のムーア・マシンの状態の出力シンボルを出力するよう出力関数を設定すれば、ミーリ・マシンに容易に変換できる。ミーリ・マシンの状態はそこに遷移してくる矢印ごとに異なる出力ラベルが設定されているため、逆の変換はそれほど単純ではない。その場合は、出力シンボルごとに状態を設定してやる必要がある。