問 題
図は、入力記号の集合が{0、1}であり、二つの内部状態をもつ非決定性有限オートマトンの状態遷移図である。この非決定性有限オートマトンと等しい決定性有限オートマトンの状態遷移図として最も妥当なのはどれか。
ただし、図において、太い矢印が示す状態は初期状態を、二重丸で表された状態は受理状態をそれぞれ表す。なお、二つの有限オートマトンが等しいとは、それらが受理する記号列の集合が等しいことを意味する。
正解 (1)
解 説
初期状態を「状態１」、受理状態を「状態２」と名付けます。状態１においてこのオートマトンは「 0 を与えると、状態１のままかもしれないし、受理状態の状態２に遷移するかもしれない」という図になっています。同様に、「状態２において、１を受け取るとそのままかもしれないし、状態１に遷移するかもしれません」。
具体的入力の結果をふまえ、特徴的な選択肢から検討します。
「１を入力」すると、受理されません。選択肢 3,5 のオートマトンだと、「1 を入力で受理されてしまう」ため、誤りです。
「00 を入力」すると、初めの 0 で状態１のままで、次の 0 で状態２に遷移すれば受理します。選択肢 4 のオートマトンだと 、「00 で 100% 受理できない」ので、誤りです。
「01 を入力」すると、初めの 0 で状態 2 にいって、次の 1 で状態 2 のままであれば受理します。選択肢 2 のオートマトンだと、 「01 で 100% 受理できない」ので、誤りです。
以上より、正解は 1 です。
コメント