平成21年度春期 情報処理安全確保支援士 午前Ⅰ 問2

「すごろく」みたいに、入力された文字の順にコマを動かしてゴールを目指おう

有限オートマトンは、状態遷移図という「すごろく」のマスの上を、文字が来るたびに対応する矢印に進めていく仕組み。文字を全部読み終わったときに、二重丸の「ゴール（受理状態）」に止まっていれば成功（受理）だよ。

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

適当に見分けるのではなく、選択肢の文字（0や1の並び）を1文字ずつ指で追って、ちゃんと二重丸のマスで終わるものを探し出そう。

Finite Automaton Trace

to determine acceptance in a finite automaton、 follow transitions from the start state and check whether the final state is accepting

start state\nfollow each symbol\nend in accept state

確認ポイント

• 途中状態だけで判断しない。
• 最後に受理状態へ着くかを確認する。
• 入力列を順にトレースする。

正解

ウ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

1011は不正解だよ。S1から「1→0→1→1」とたどると、S1→S2→S2→S1→S2になって、最後が受理状態のS3に着かないんだ。受付窓口に行きたいのに、別の窓口で順番が終わってしまうイメージだよ。

選択肢イ

1100は不正解だよ。スタート地点S1から「1→1→0→0」と順番に進むと、S1→S2→S1→S3→S2となって、最後がゴールのS3ではなくS2で止まるんだ。駅の乗換えで、最後に目的駅の一つ手前で降りちゃった感じだね。

選択肢ウ（正解）

1101は正解だよ。S1から「1→1→0→1」と進むと、S1→S2→S1→S3→S3となって、最後に受理状態のS3にいるんだ。迷路でいうと、最後の一歩を踏んだ時点でちゃんとゴール部屋に入れているからOKだよ。

選択肢エ

1110は不正解だよ。S1から「1→1→1→0」と進むと、S1→S2→S1→S2→S2になり、最後はS3ではなくS2なんだ。鍵穴に合う順番を試しても、最後に正しい部屋へ入れていないので受け付けられない、という感じだよ。