平成26年度春期 プロジェクトマネージャ 午前Ⅰ 問2

有限オートマトンと状態遷移表

表の読み方と、ビット列を読み込む過程の記録方法を準備しましょう。

この問題で問われていること

異なる入力列を状態遷移表で追跡し、その経路を比較するには、どのように記録すればよいでしょうか。

有限オートマトンと状態遷移表

異なる入力列を状態遷移表で追跡し、その経路を比較するには、どのように記録すればよいでしょうか。

確認ポイント

• 状態遷移表の行・列・各欄は、それぞれ何を表しているでしょうか。
• 開始状態はどの記号で示され、最初の入力では表のどこを参照するでしょうか。
• 例として000と010を読み込むとき、各ビットを読む前後の状態をどう書き並べられるでしょうか。 入力列の前に別のビット列を付けた場合、続きの追跡に必要な状態をどのように求められるでしょうか。

正解

ウ

解説

添付の公式解答表では，問2の正解はウ。状態遷移表は添付の公式問題ページを参照する。受理状態は，入力全体を読み終えた時点の状態で判断する。末尾の 110 に注目すると，最初の 1 で b または d，次の 1 で必ず d，最後の 0 で c に移る。末尾より前の入力によらず c に到達するので，受理状態は c となる。

添付の公式解答表では，問2の正解はウ。状態遷移表は添付の公式問題ページを参照する。受理状態は，入力全体を読み終えた時点の状態で判断する。末尾の 110 に注目すると，最初の 1 で b または d，次の 1 で必ず d，最後の 0 で c に移る。末尾より前の入力によらず c に到達するので，受理状態は c となる。

選択肢ア

誤り。末尾の 11 を読み終えた状態は d であり，続く 0 によって c に移るため，読み終えた状態は a ではない。

選択肢イ

誤り。a または c で 1 を読むと b に移るが，次の 1 で d，最後の 0 で c に移る。b は末尾の 110 を読み終えた状態ではない。

選択肢ウ（正解）

正しい。どの状態からでも 1 を続けて二つ読むと d に到達し，続く 0 で c に移る。したがって，末尾の 110 を読み終えた状態 c を受理状態とする。

選択肢エ

誤り。d は末尾の 11 を読み終えた時点の状態である。その後，最後の 0 を読むと c に移る。

学習のポイント

異なる入力列を状態遷移表で追跡し、その経路を比較するには、どのように記録すればよいでしょうか。