修了試験 2012-12-16実施分 基本情報技術者試験 問4

解説

正解は3です。 有限オートマトンは、入力文字に従って状態を移り、最後に受理状態にいれば文字列を受理します。 図の状態を次のように呼んで遷移を整理します。 初期状態をS0、上の状態をS1、右の状態をS2、二重丸の受理状態をS3、右下の状態をS4とします。 S0は0でS0のまま、1でS1へ移ります。 S1は0でS0へ戻り、1でS2へ移ります。 S2は0でS0へ戻り、1でS3へ移ります。 S3は0でS0へ戻り、1でS4へ移ります。 S4は0でも1でもS4にとどまり、抜け出せません。 【選択肢別解説】 1：× 01011はS0、S0、S1、S0、S1、S2の順に移ります。 最後がS2で受理状態ではないため、受理されません。 2：× 01111はS0、S0、S1、S2、S3と進み、5文字目の1でS4へ移ります。 S4から抜け出せないため、受理されません。 3：○ 10111はS0、S1、S0、S1、S2、S3の順に移ります。 最後が受理状態S3なので、受理されます。 4：× 11110は4文字目の1でS4に入ります。 S4は0でもS4のままなので、受理されません。 【ポイント】 この図は「1がちょうど3個連続して終わる文字列」を受理し、1が4個以上連続すると脱出できない状態に入ります。 遷移を1文字ずつ書き出してたどれば、確実に判定できます。