出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
決定性有限オートマトン(3状態、初期状態が受理状態)が0100を受理するために、破線で囲まれたア、イ、ウ、エの遷移に割り当てるべき入力(0/1)の組合せを選ぶ問題。
決定性のオートマトンでは、1つの状態から、同じ入力に対して遷移先が1つに定まることを使い、入力の割当てを決める問題。
① 決定性オートマトン: 1つの状態から出る矢印は、0と1で別々になる。受理させたい列(0100)を実際にたどって、矢印の記号を決める
② S0で0→S0のまま(ア=0、イ=1)、1→S1、0→S2、最後の0→S0に戻る(エ=0、ウ=1)
③ ア0・イ1・ウ1・エ0(④)
状態を、初期状態(受理状態)をS0、右上をS1、下をS2とする。S0には、自己ループ(ア)と、S1への遷移(イ)があり、決定性なので、アとイは異なる入力(0と1)である。S1からS2へは、0でも1でも遷移する。S2には、S1への遷移(ウ)と、S0への遷移(エ)があり、ウとエも異なる入力である。0100を受理するには、S0から始めて、0でS0のまま(ア=0)、1でS1(イ=1)、0でS2、最後の0で、S0(受理状態)に戻る(エ=0)必要がある。このとき、ウ=1となる。したがって、ア=0、イ=1、ウ=1、エ=0の④が正しい。
■ 決定性有限オートマトンの読み方
丸が「状態」、矢印が「入力(0か1)を1文字読んだときの移り先」です。二重丸は受理状態で、入力を全部読み終えたときに受理状態にいれば、その入力列を「受理する」といいます。
■ 決定性とは
どの状態でも、入力0と入力1のそれぞれについて、移り先がちょうど1つずつ決まっているという意味です。そのため、同じ状態から出るアとイは異なる入力(一方が0なら他方は1)、ウとエも異なる入力になります。
決定性有限オートマトンでは、各状態で、各入力記号に対する遷移が、ちょうど1つ。文字列を先頭から1文字ずつ入力して、最後に受理状態にいれば受理される。
キーワード: 決定性有限オートマトン、状態遷移、受理状態、入力記号、オートマトン、形式言語、情報工学部門