完全なオートマトン

有限オートマトンの基本の定義では、すべての状態から、すべての記号について遷移がある必要はありません。完全なオートマトン（全域的なオートマトンともいいます）とは、すべての状態から、入力アルファベットのすべての記号について遷移が定義されているオートマトンのことです。

完全なオートマトンのつくり方

次のオートマトン A = ⟨Q, Σ, δ, q₀, F⟩ を考えます。

この図には、状態 q₀ から文字「b」の遷移がかかれていません。入力がこの遷移を必要とする場合は、オートマトンはその入力語を受理しないことにします。しかし、形式化の観点からは、遷移関数 δ がいくつかの値に対して定義されていないのは好ましくないことがあります。ここでは、例えば δ(q₀, b) が定義されていません。

これは、状態を1つ増やした等価なオートマトンをつくれば簡単に解決できます。「足りない」遷移はすべてこの状態に向かい、この状態は受理状態ではなく、その後の入力はすべてこの状態で自己ループします。このオートマトンを完全なオートマトンといいます。修正した等価なオートマトンは、例えば次のようになります。

状態 q_fail を加えました。ほかの状態からこの状態への遷移は、もとのオートマトンでその遷移がなかった場合に限って加えています。この状態は受理状態ではなく、その後のすべての入力に対して自己ループします。もとのオートマトンでは遷移が足りずに止まってしまう場面でも、このオートマトンには足りない遷移がなく、状態 q_fail に移ります。

したがって、一般性を失うことなく、オートマトンには状態とアルファベットの文字のすべての組合せについて遷移が定義されていると、いつでも仮定できます。

定義

完全なオートマトン A = ⟨Q, Σ, δ, q₀, F⟩ については、次が成り立ちます。

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$

参考文献

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools