有限オートマトンが受理する入力列
有限オートマトンが受理する入力列出題分類：基礎理論 > 情報に関する理論
［出題：平成21年春／AP午前問3］※「AP」は応用情報技術者試験を表す略号です。
初期状態（→）からスタートし、1ビットずつ消費して、受理状態で終わればOK。
正解は「ウ」
これで解ける
オートマトンとは、ある状態に対して何らかの入力を受け付けた結果、状態が遷移するといった内容を表すもので、状態とその変化を状態遷移図などで表します。
問題文の図では、太い矢印が開始状態（S1）で、「1」の変化があるとS2へ状態が遷移することを表しています。最終的に◎のS3で入力が終了すると「受理」と呼ばれる状態になります。
上記問題の状態遷移図の初期状態と受理状態を意識しながら、丁寧にトレースすれば、答えを求められます。
- 選択肢ア S1から1011だと、最後はS2の状態になる。
- 選択肢イ S1から1100だと、S3を経由して最後はS2の状態になる。
- 選択肢ウ S1から1101だと、最後はS3の状態になる（受理）。
- 選択肢エ S1から1110だと、最後はS2の状態になる。
よって、正解は「ウ」です。
ハミング符号
ハミング符号出題分類：基礎理論 > 通信に関する理論
［出題：平成24年秋／AP午前問3］
丁寧に代入すべし！mod2が0の式に含まれず、mod2が1の式全てに含まれるビットが、誤りビット
正解は「エ」
理解を深める
問題文にある y1 y2 y3 y4 y5 y6 y7 = 1100010 を具体的に代入して考えます。
(y1＋y2＋y3＋y5) mod 2 → (1＋1＋0＋0) mod 2 = 2 mod 2 = 0
(y1＋y2＋y4＋y6) mod 2 → (1＋1＋0＋1) mod 2 = 3 mod 2 = 1
(y2＋y3＋y4＋y7) mod 2 → (1＋0＋0＋0) mod 2 = 1 mod 2 = 1
つまり、2つ目、3つ目が0になっていないため、誤りがあることがわかります。2つ目、3つ目の式に共通する情報ビットは「y4」です。したがって、y4を修正します。
y1 y2 y3 y4 = 1100 → 1101
よって、正解は「エ」となります。
ビット誤り
ビット誤り出題分類：基礎理論 > 通信に関する理論
［出題：平成24年春／AP午前問5］
水平垂直パリティは、誤り行と誤り列の交差する1ビットだけ訂正できる。複数の誤りは検出だけ。
正解は「ア」
理解を深める
パリティビットとは、1のビット数が奇数個または偶数個になるように調整するビットを付加し、誤りを検出するものです。パリティビットを付加する方向により、「垂直パリティ」と「水平パリティ」の2種類があります。
パリティビットを使っても基本的には、誤りを訂正することはできませんが、水平・垂直の両方向にパリティを付加する「水平垂直パリティチェック方式」であれば、行・列が交差した点の1ビットの訂正が可能になります。
