SC情報処理安全確保支援士試験 午前Ⅰ

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

問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。

問題

表は,入力記号の集合が {0、 1},状態集合が {a、 b、 c、 d} である有限オートマトンの状態遷移表である。長さ 3 以上の任意のビット列を左(上位ビット)から順に読み込んで最後が 110 で終わっているものを受理するには,どの状態を受理状態とすればよいか。
入力0及び1に対する状態a,b,c,dの遷移先を示す状態遷移表。
入力0及び1に対する状態a,b,c,dの遷移先を示す状態遷移表。

選択肢

  1. ア
    a
  2. イ
    b
  3. ウ
    c
  4. エ
    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による補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針