平成28年度秋期 ITサービスマネージャ 午前Ⅰ 問2

状態が記憶する直前の入力を追跡する

有限オートマトンでは、各状態がそれまでの入力について何を区別しているかを把握することが判断の鍵になります。遷移の定義に沿って入力を一文字ずつたどり、どの状態に到達するかを自分の手で確認する姿勢を意識しましょう。

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

問われているのは、ある末尾の並びで入力が終わったときに到達する状態がどれかという観点です。途中経過に惑わされず、開始状態や任意の状態から入力をたどっても同じ状態に行き着くかどうかを確かめることが大切です。

視点

有限オートマトンは、現在の状態と次の入力記号だけで次の状態が決まる仕組みです。そのため、各状態は過去の入力のうち判断に必要な情報だけを保持しているとみなせます。末尾のパターンを扱う場面では、直前の数文字が状態にどう反映されるかを意識すると整理しやすくなります。結論を急がず、遷移の定義に従って実際に入力を追う作業を重ねることが理解の土台になります。

確認ポイント

• 遷移の定義に従い、入力記号を一文字ずつ適用して到達する状態を記録したか
• 開始状態以外の状態から同じ末尾の並びを入力しても、到達先が変わらないか確かめたか
• 末尾の並びの直前に別の記号が続く入力例も試し、到達先の状態を比べたか

正解

ウ

解説

状態遷移表では、aとcの行、bとdの行がそれぞれ同じ内容だよ。そのため、読み終えた状態は直前の2ビットだけで決まるんだ（00→a、01→b、10→c、11→d）。110で終わる列は、どの状態から読み始めても必ずcで終わるので、正答はウのcだよ。

表の読み取り

公式の状態遷移表はこうなっているよ。aは0でa、1でbへ移る。bは0でc、1でdへ移る。cは0でa、1でbへ移る。dは0でc、1でdへ移る。aとcの行が同じで、bとdの行も同じなのがポイントだよ。

状態が表す意味

0を読むと、aかcからはaへ、bかdからはcへ移るよ。1を読むと、aかcからはbへ、bかdからはdへ移る。bとdに入るのは1を読んだ直後だけで、aとcに入るのは0を読んだ直後だけなんだ。だから2ビット以上読んだ後の状態は、最後の2ビットで決まるよ。00ならa、01ならb、10ならc、11ならdだね。

110で終わる場合

問題文と表には開始状態が示されていないから、どの状態から始めても成り立つかを確かめよう。110の最初の1を読むとbかdに移り、次の1でdに移り、最後の0でcに移るよ。だから長さ3以上で110で終わる列は、必ずcで読み終わるんだ。

比較と注意点

a・b・dは、それぞれ最後の2ビットが00・01・11の列を読み終えた状態なので、110で終わる列の最終状態にはならないよ。ただし、この表では010で終わる列もcで読み終わるんだ。cだけを受理状態にしても110で終わる列だけに絞れるわけではない点に注意しよう。選択肢の中で、110で終わる列を必ず受理できる状態はcだけだよ。

選択肢ア

これは不正解だよ。状態aに入るのは、aかcの状態で0を読んだときだけだよ。aとcはどちらも直前に0を読んだ後の状態なので、aは最後の2ビットが00の列を読み終えた状態になるんだ。110で終わる列は最後の2ビットが10なので、aで読み終わることはないよ。

選択肢イ

これは不正解だよ。状態bに入るのは、aかcの状態で1を読んだときだよ。aとcは直前に0を読んだ状態なので、bは最後の2ビットが01の列を読み終えた状態になるんだ。110で終わる列は最後に0を読むから、1を読んだ直後にしか入らないbで読み終わることはないよ。

選択肢ウ（正解）

これは正解だよ。110の最初の1を読むと、どの状態からでもbかdに移るよ。次の1ではbからもdからもdに移り、最後の0でdからcへ移るんだ。だから長さ3以上で110で終わる列は、開始状態に関係なく必ずcで読み終わるよ。なお010で終わる列もcに入るけど、選択肢の中で条件を満たすのはcだけだよ。

選択肢エ

これは不正解だよ。状態dに入るのは、bかdの状態で1を読んだときだよ。bとdは直前に1を読んだ状態なので、dは最後の2ビットが11の列を読み終えた状態なんだ。110の11まで読んだ時点ではdにいるけど、最後の0でdからcへ移るから、読み終えたときの状態はdではないよ。

学習のポイント

開始状態が示されていない状態遷移表から、各状態が直前の入力のどの部分を覚えているかを読み取る力を確認しよう。