BNF式
BNF式出題分類：基礎理論 > 情報に関する理論
［出題：平成24年春／AP午前問3］
DNAはコドンの1つ以上の連続、コドンは塩基の3つの連続、塩基は1文字のため、文字数は3の倍数
正解は「ウ」
理解を深める
BNF（バッカス・ナウア）記法とは、形式言語と呼ばれるものの1つで、プログラム言語やネットワークで使用される規則などを規定する記述法です。BNFは「＜概念＞::＝」の形式で定義されます。また、「｜」で「または」を表現します。
問題の式から、DNAは＜コドン＞単体、または＜コドン＞が複数つながったものと解釈できます。次に、コドンは＜塩基＞が3つつながったものと解釈できます。さらに、塩基はA、T、G、Cのいずれかの1文字です。つまり、＜コドン＞は3の倍数個のアルファベット（A、T、G、C）で構成されていることが分かります。
コドンが3文字のアルファベットということは、DNAとして示される文字列は3の倍数個の文字で形成されなければなりません。この条件を満たすものは、選択肢ウしかありません。
BNFの例
BNFの例| 記述する内容 | BNFによる記述 |
|---|---|
| 数値は0か1である | ＜数値＞::＝0｜1 |
| 4ケタの数値をIDとする | ＜ID＞::＝＜数値＞＜数値＞＜数値＞＜数値＞ |
| 数列は1回以上の数値の繰り返し | ＜数列＞::＝＜数値＞｜＜数列＞＜数値＞ |
逆ポーランド表記法
逆ポーランド表記法出題分類：基礎理論 > 情報に関する理論
［出題：平成24年秋／AP午前問4］
後置は、左から演算子を探す、見つけたら、直前の2項で演算する
正解は「イ」
これで解ける
逆ポーランド表記法は、主にコンピュータで計算させる数式を記述する方法です。後置表記法ともいわれます。一方、人がふだん数式に利用しているのは、演算子を数値の間に入れる中置記法です。
逆ポーランドで表現するための基本は、a＋b を ab＋ で表すことにあります。また、1回変換した部分は、変換後の1つの項とみなすことに注意して、式を組み立てていきます。その際には、通常の計算式と同じ優先順位で計算していきます。
この問題では式の左から演算子があるところまで見ていき、直前の演算対象の項を2つさかのぼって取り出すことで答えが導けます。
- 選択肢ア 最初に演算子があるため、逆ポーランド表記法に該当しない。誤り。
- 選択肢イ ＋が見つかり、ＡＢ＋、すなわちＡ＋Ｂが最初に計算する項になる。
- 選択肢ウ －が見つかり、ＡＢ－、すなわちＡ－Ｂが最初に計算する項になる。誤り。
- 選択肢エ ×が見つかり、ＢＣ×、すなわちＢ×Ｃが最初に計算する項になる。誤り。
よって、正解は「イ」です。
中置記法から逆ポーランドへ変換する流れ
中置記法を逆ポーランド表記法にするには、通常の式の優先度順に式を見ていき、A+B を [AB＋] などと括弧を書いて、1つの項としながら見ていくとわかりやすいです。
E＝(A＋B)×(C－D) → E＝[AB+]×[CD－]
E＝[AB+]×[CD－] → E＝[[AB+] [CD－]×]
E＝[[AB+] [CD－]×] → [E [[AB+] [CD－]×]＝]
最後に、括弧をすべて削除して並べます。
[E[[AB+] [CD－]×]＝] → EAB+CD－×＝
おわりに
今回取り上げた問題のキーワードは、以下のとおりです。
- 有限オートマトン
- ハミング符号
- パリティビット
- CRC
- ハフマン符号化
- サンプリング量の計算
- バッカス・ナウア記法
- 逆ポーランド記法
暗記系の問題というよりも、パズル系、計算系の問題でした。これらの問題は形を変えて、値を変えて何回も出題されている重要な問題です。このスピードアンサーを読んだ後、必ず過去問に取り組んでください。似たような問題が多く出題されていることがわかるかと思います。
過去問演習を繰り返すことで、知識を定着させましょう。
