平成26年度 春期 応用情報技術者 問4

正解 ウ

どの状態から始めても、1を2回読むとd、続けて0を読むとcになります。110で終わるビット列は必ずcで終わるので、cを受理状態にします。

表の1の列を見ると、どの状態からでも1を読むとbかdに移ります。b、dから1を読むとdなので、11を読んだ直後は必ずdです。dから0を読むとcに移るため、110で終わるビット列はどの状態から読み始めても最後にcに着きます。つまり、末尾の3ビットを順に追えば、読み始めの状態を決めなくても答えが決まります。

ア：aは、a、cから0を読んだときの状態で、末尾が00のビット列で到達します。110の最後の0は、dから読むのでcに移ります。

イ：bは、a、cから1を読んだときの状態で、最後の1ビットが1のときに到達します。110のように0で終わるビット列はbに着きません。

エ：dは、11を読んだ直後の状態です。最後の0を読むとdからcに移るので、110の受理状態はdではありません。

出典：平成26年度 春期 応用情報技術者試験 問4