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

受理条件を考える一つの視点

有限オートマトンの受理条件を検討するときは、入力の読み進め方と最終的な状態の対応に注目し、途中の印象だけで判断せず、与えられた定義に沿って全体を丁寧に確認します。

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

確認する観点を、入力を最後まで処理した時点でどの情報が判定に関わるか、という一点に絞ります。状態遷移の過程と最終判定を分け、それだけを丁寧に一度整理してください。

視点

受理を考える際は、入力記号を順に追った結果と、判定に使われる情報を切り分けて整理します。途中で通過した状態や印象に引きずられず、問題中の定義との対応を一つずつ確認しましょう。

確認ポイント

• 入力を最初から最後まで追ったとき、判定に必要な情報を一貫して記録できているか確認する。
• 途中の状態と、処理終了時に参照すべき状態を混同していないか確認する。
• 判断の根拠が、問題中で示された受理の定義と直接対応しているか確認する。

正解

ウ

解説

有限オートマトンは、入力列を左から一文字ずつ読み、矢印のラベルに従って状態を遷移します。すべての入力を読み終えた時点でS3にいれば受理されます。

理由

S1を初期状態として入力を左から順に処理します。各記号に対応する遷移をたどり、最後の入力を読んだ後の状態がS3である場合に限って受理されます。

比較

各列を同じ手順で追跡すると、1101だけが最終的にS3で終了します。他の列は最後にS1またはS2で終了するため、受理状態には到達しません。

選択肢ア

これは不正解だよ。入力列「1011」を左から追うと，S1で1を読みS2，続く0でS2に留まり，1でS1へ戻り，最後の1でS2に移る。終了時は受理状態S3ではないため，この列は受理されない。

選択肢イ

これは不正解だよ。入力列「1100」では，S1から1でS2，次の1でS1に戻る。その後0でS3に到達するが，最後の0を読むとS3からS2へ移る。読み終えた状態がS3ではないので，受理条件を満たさない。

選択肢ウ（正解）

これは正解だよ。入力列「1101」は，S1から1でS2，次の1でS1，0でS3へ進み，最後の1ではS3のループを通る。全て読み終えた状態が受理状態S3なので，この入力列は受理される。

選択肢エ

これは不正解だよ。入力列「1110」では，S1から最初の1でS2，次の1でS1，さらに1でS2へ移る。最後の0はS2のループなので，終了状態はS2のままであり，受理状態S3に到達していない。

学習のポイント

状態遷移を表にして、最後の状態だけで受理・不受理を判定する練習をします。