オートマトンと状態遷移図＜ハードウェアとソフトウェア＜Ｗｅｂ教材＜木暮仁

キーワード オートマトン、チューリングマシン、状態遷移図、状態遷移表 オートマトン（automaton）とは、入力に対して内部の状況に応じた処理を行った結果を出力する仮想的な自動機械の概念です。オートマトンのうち、状態の個数と入力の個数が有限個の場合を有限オートマトンといいます。 処理に伴い、内部の状態が変化する（遷移といいます）ので、同じ入力でも異なる処理、異なる出力になります。それで、どの状況のときに、どの入力があると、どの状態に遷移するかを示す規則が必要になります。それを表形式にしたものを状態遷移表、図の形式にしたものを状態遷移図といいます。 有限オートマトンでは、開始をするときの状態と終了するときの状態が決められており、開始状態で最初の入力が行われ、入力の最後で決められた状態（受理状態という）になる（受理されたという）ことが求められます。 有限オートマトンを、テープの先頭から読み込

[kikuchinomegane]

オートマトン、状態遷移図