修了試験 2016-06-12実施分 基本情報技術者試験 問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がちょうど3個連続して終わる文字列だけが受理されます。 【選択肢別解説】 1：× 01011は、S0、S1、S0、S1、S2と移り、受理状態でないS2で終わります。 2：× 01111は、S0、S1、S2、S3と進んだ後、4個目の1でS4に入り受理されません。 3：○ 10111は、S1、S0、S1、S2、S3と移り、受理状態S3で終わります。 4：× 11110は、4個目の1でS4に入り、最後の0でもS4のままなので受理されません。 【ポイント】 オートマトンの問題は、1文字ずつ状態を書き出してたどるのが確実です。 抜け出せない状態に入った文字列は、その後の入力にかかわらず受理されません。