SC情報処理安全確保支援士試験 午前Ⅰ
平成26年度春期 情報処理安全確保支援士 午前Ⅰ 問2
問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。
問題

選択肢
- アa
- イb
- ウc
- エd
解き方のヒントを見る
有限オートマトンと状態遷移表
表の読み方と、ビット列を読み込む過程の記録方法を準備しましょう。
この問題で問われていること
異なる入力列を状態遷移表で追跡し、その経路を比較するには、どのように記録すればよいでしょうか。
有限オートマトンと状態遷移表
異なる入力列を状態遷移表で追跡し、その経路を比較するには、どのように記録すればよいでしょうか。
確認ポイント
- 状態遷移表の行・列・各欄は、それぞれ何を表しているでしょうか。
- 開始状態はどの記号で示され、最初の入力では表のどこを参照するでしょうか。
- 例として000と010を読み込むとき、各ビットを読む前後の状態をどう書き並べられるでしょうか。 入力列の前に別のビット列を付けた場合、続きの追跡に必要な状態をどのように求められるでしょうか。
正解と解説を見る
正解
ウ
解説
問2の正解はウです。状態遷移表は問2を参照する。受理状態は,入力全体を読み終えた時点の状態で判断する。末尾の 110 に注目すると,最初の 1 で b または d,次の 1 で必ず d,最後の 0 で c に移る。末尾より前の入力によらず c に到達するので,受理状態は c となる。
正答
正解はウの c です。有限オートマトンは,入力を 1 ビットずつ読むたびに状態が移り,読み終えた時点の状態で受理かどうかを判定する。末尾が 110 で終わるビット列を読み終えたとき,必ず同じ状態に到達する必要がある。どの状態から始めても,1 を二つ続けて読むと d に到達する(任意の状態 → 1 → 1 → d)。そのあと 0 を読むと c に移る(d → 0 → c)。したがって,末尾の 110 を読み終えた状態は c であり,c を受理状態とすればよい。
誤答の理由
ア:誤りです。末尾の 11 を読み終えた状態は d であり,続く 0 によって c に移る。読み終えた時点で a にはならないため,受理状態には適さない。
イ:誤りです。a または c で 1 を読むと b に移るが,次の 1 で d に進み,最後の 0 で c に移る。b は末尾の 110 を読み終えた状態ではありません。
エ:誤りです。d は末尾の 11 を読み終えた時点の状態にすぎない。最後の 0 を読むと c に移るため,末尾の 110 を読み終えた状態は d ではありません。
整理
受理状態は「入力を読み終えた時点の状態」で決まる。末尾のパターンを読み切ったときに,どの状態から始めても必ず到達する状態を選ぶとよい。110 の場合は「1,1 で d,0 で c」と一本道で追うと覚えやすい。
選択肢ア
誤り。末尾の 11 を読み終えた状態は d であり,続く 0 によって c に移るため,読み終えた状態は a ではない。
選択肢イ
誤り。a または c で 1 を読むと b に移るが,次の 1 で d,最後の 0 で c に移る。b は末尾の 110 を読み終えた状態ではない。
選択肢ウ(正解)
正しい。どの状態からでも 1 を続けて二つ読むと d に到達し,続く 0 で c に移る。したがって,末尾の 110 を読み終えた状態 c を受理状態とする。
選択肢エ
誤り。d は末尾の 11 を読み終えた時点の状態である。その後,最後の 0 を読むと c に移る。
学習のポイント
異なる入力列を状態遷移表で追跡し、その経路を比較するには、どのように記録すればよいでしょうか。
解説を確認したら、演習モードや同じ分野の類題で理解を定着させましょう。
出典:独立行政法人 情報処理推進機構(IPA)平成26年度春期 情報処理安全確保支援士試験 午前Ⅰ 問2(公式資料:問題冊子(PDF) / 解答例)
関連する過去問一覧
IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針