📘【完全解説】応用情報技術者 平成29年秋期 午前問2
BNF・形式言語・オートマトン・mod計算を横断理解する120点解説
📘 応用情報技術者 平成29年秋期 午前問2【問題文】
次のBNFにおいて、非終端記号 <A> から生成される文字列はどれか。
<R1> ::= 1 | 4 | 7
<R2> ::= 2 | 5 | 8
<A> ::= <R0> | <A><R0> | <B><R2> | <C><R1>
<B> ::= <R1> | <A><R1> | <B><R0> | <C><R2>
<C> ::= <R2> | <A><R2> | <B><R1> | <C><R0>
■ 選択肢
- ア：123
- イ：124
- ウ：127
- エ：128
📝 問題（BNF定義）
<R0> ::= 0 | 3 | 6 | 9 <R1> ::= 1 | 4 | 7 <R2> ::= 2 | 5 | 8 <A> ::= <R0> | <A><R0> | <B><R2> | <C><R1> <B> ::= <R1> | <A><R1> | <B><R0> | <C><R2> <C> ::= <R2> | <A><R2> | <B><R1> | <C><R0>
選択肢：ア 123 / イ 124 / ウ 127 / エ 128
🔎 基礎理論：BNFとは何か？
BNF（Backus–Naur Form）は文脈自由文法を記述する形式。コンパイラの構文解析や形式言語理論で使用される。
- 非終端記号：<A> など
- 終端記号：実際の数字
- | は OR（選択）
📊 数字の分類（mod3構造）
| 非終端 | 数字 | 3で割った余り |
|---|---|---|
| R0 | 0,3,6,9 | 0 |
| R1 | 1,4,7 | 1 |
| R2 | 2,5,8 | 2 |
このBNFは「3で割った余り」の状態遷移を表している。
🔄 <A> <B> <C> の意味
| 非終端 | 意味 |
|---|---|
| <A> | 3で割って0余り |
| <B> | 3で割って1余り |
| <C> | 3で割って2余り |
これはDFA（決定性有限オートマトン）と等価な構造である。
🧮 なぜ桁和で判定できる？
abc = 100a + 10b + c 100 ≡ 1 (mod 3) 10 ≡ 1 (mod 3) → abc ≡ a + b + c (mod 3)
📌 各選択肢の計算
| 選択肢 | 計算 | 余り | 状態 |
|---|---|---|---|
| 123 | 1+2+3=6 | 0 | <A> |
| 124 | 1+2+4=7 | 1 | <B> |
| 127 | 1+2+7=10 | 1 | <B> |
| 128 | 1+2+8=11 | 2 | <C> |
✅ 結論
<A> は「3で割って0余り」の数を生成する。
🚀 応用情報レベルで押さえるべき論点
- BNFと文脈自由文法の理解
- 文法とオートマトンの等価性
- mod計算と状態管理
- 再帰規則＝状態遷移
💡 具体的な使用状況（実務との接点）
- コンパイラの構文解析（LL/LR構文解析）
- 入力値検証ロジックの設計
- 通信プロトコルの文法定義
- 数値チェックアルゴリズム（チェックディジット設計）
📚 さらに発展
- チョムスキー標準形への変換
- 正規文法との違い
- DFAへの変換手順
📝 要点まとめ
- R0/R1/R2は3で割った余り分類
- A/B/Cは剰余状態
- 桁和で判定可能
- 正解は123
- 本質は「形式文法×数論」の融合問題
✍ 後書き｜関連知識・出題傾向・背景理解
本問は一見すると複雑な再帰的BNFの読解問題ですが、本質は 「形式文法と剰余（mod）計算の対応関係を見抜けるか」 にあります。
📚 関連する重要事項
- BNF（Backus–Naur Form）と文脈自由文法（CFG）
- チョムスキー階層（正規文法・文脈自由文法・文脈依存文法）
- DFA（決定性有限オートマトン）との等価性
- 状態遷移と再帰規則の関係
- mod計算（特に3で割った余りの性質）
🔎 背景知識として重要なポイント
10進数においては 10 ≡ 1 (mod 3) という性質があるため、 「3で割れるかどうか」は各桁の和で判定できます。 本問ではこの数論的性質を、形式文法の状態遷移として表現しています。
つまり、 <A>・<B>・<C> は“剰余状態”を表す非終端記号 であり、再帰規則はそのまま状態遷移を意味しています。
📈 応用情報における出題傾向
- BNFの直接読解問題は周期的に出題される
- オートマトンや正規表現との関連問題が頻出
- 数値規則（偶奇・倍数・剰余）と形式言語の融合問題が多い
- 「構造を抽象化して本質を見抜く力」が問われる
💡 学習アドバイス
BNF問題では、文字列を機械的に展開するのではなく、 「この文法は何を判定しているのか？」という 意味レベルの理解が重要です。
形式言語はコンパイラ理論・入力検証・プロトコル設計など 実務とも深く関わる分野です。試験対策としてだけでなく、 情報科学の基礎教養として体系的に理解しておくと、 午前・午後の両方で大きな武器になります。
本問は「BNFの読解問題」ではなく、 形式文法 × オートマトン × 数論（mod計算） を横断的に理解しているかを問う良問である。
⚠ ひっかけ対策｜一問一答チェックテスト
応用情報技術者試験で狙われやすい“思考の落とし穴”を確認しましょう。
Q1. <A>は「数字の並びが0で終わる文字列」を表している。
答え：✕
R0には0,3,6,9が含まれるため「0で終わる」とは限らない。本質は「3で割った余り0の状態」である。
Q2. <A><R0> という規則は単なる桁追加であり、状態は変化しない。
答え：〇
R0は3で割って余り0なので、状態（剰余）は変化しない。ここが状態遷移の本質。
Q3. この問題はBNFを機械的に展開しないと解けない。
答え：✕
本質はmod3構造に気づくこと。数論的意味を理解すれば高速に解ける。
Q4. <B>は3で割った余り2の状態を表す。
答え：✕
<B>は余り1、<C>が余り2。ここは典型的な取り違えポイント。
Q5. 124は<A>から生成可能である。
答え：✕
1+2+4=7 → 3で割って余り1。よって<B>であり<A>ではない。
Q6. BNFはオートマトンと無関係である。
答え：✕
文法とオートマトンは等価関係にある。本問はDFA的構造をBNFで表現している。
「BNFを展開する問題」と思い込ませて、
実際は“剰余状態の遷移問題”である点。
🚀 発展解説｜DFA・チョムスキー標準形・正規文法・コンパイラ理論との接続
① DFA（決定性有限オートマトン）としての説明
本問の <A>・<B>・<C> は、それぞれ 「3で割った余り」を表す状態と解釈できる。
- <A> ：余り0
- <B> ：余り1
- <C> ：余り2
各桁（R0, R1, R2）を読むたびに状態が遷移する。 例えば現在<A>（余り0）の状態でR1を読むと、 新しい余りは「0 + 1 ≡ 1 (mod3)」となり<B>へ遷移する。
再帰規則 ＝ 状態遷移関数 δ(q, a)
したがってこのBNFは、 3の倍数判定DFAを文法で記述したもの といえる。
② チョムスキー標準形（CNF）への変換
チョムスキー標準形では、生成規則は次の2形式に限定される：
- A → BC（非終端2つ）
- A → a（終端1つ）
本問のBNFはほぼCNFに近いが、 「<A> → <A><R0>」のような形はそのまま使用可能。 ただし R0 → 0 | 3 | 6 | 9 などの部分は 終端生成規則に分解する必要がある。
CNF変換はCYKアルゴリズムによる構文解析の前提知識であり、 午後問題や高度区分での出題可能性もある。
③ 正規文法との関係
本問の文法は「右線形文法（Right Linear Grammar）」の形をしている：
A → aB A → a
これは正規文法に分類され、 正規言語と等価である。
よって：
- 正規文法 ⇔ 正規表現 ⇔ DFA ⇔ NFA
本問は文脈自由文法の形式をしているが、 実質は正規言語である点が重要。
④ コンパイラ理論との接続
BNFはプログラミング言語の構文定義に使用される。
- 字句解析（Lexical Analysis） → 正規表現・DFA
- 構文解析（Parsing） → 文脈自由文法
本問は、 「字句レベルの正規言語」と「構文レベルの文法」の橋渡し例 として理解できる。
本問は単なるBNF読解問題ではない。
DFA・正規文法・CNF・コンパイラ理論へと連なる
情報科学の基礎体系を横断的に理解しているかを問う良問である。
📚 用語完全網羅リスト｜本記事に登場した重要概念まとめ
- BNF（Backus–Naur Form）
文法を形式的に記述するための記法。プログラミング言語の構文定義に使用される。 - 非終端記号
他の記号へ展開される記号（例：<A>）。状態や構造を表す。 - 終端記号
それ以上展開されない最終的な文字（例：0〜9）。 - 文脈自由文法（CFG）
生成規則の左辺が単一非終端記号である文法。構文解析で中心的役割を持つ。 - チョムスキー階層
文法を4段階（正規・文脈自由・文脈依存・帰納的可算）に分類した理論体系。 - 正規文法
A → aB または A → a の形を持つ文法。正規言語を生成する。 - 正規言語
DFAや正規表現で表現可能な言語。計算モデルとして最も単純。 - DFA（決定性有限オートマトン）
各入力に対して遷移が一意に決まる有限状態機械。 - NFA（非決定性有限オートマトン）
同一入力で複数遷移を許すオートマトン。DFAと等価。 - オートマトン
入力列に応じて状態遷移する抽象計算モデル。 - 状態遷移関数 δ(q, a)
現在状態qと入力aから次状態を決定する関数。 - mod計算（剰余演算）
割り算の余りに着目する計算方法。本問ではmod3が本質。 - 剰余
割り算の余り。状態分類に利用される。 - 右線形文法
生成規則の右端にのみ非終端記号が現れる文法。正規文法の一種。 - チョムスキー標準形（CNF）
A→BC または A→a の形に限定した文法形式。解析アルゴリズムに利用。 - 終端生成規則
非終端から終端記号1つを生成する規則（例：A → a）。 - 再帰規則
左辺と右辺に同じ非終端が現れる規則。状態遷移や繰り返し構造を表す。 - CYKアルゴリズム
チョムスキー標準形を前提とする動的計画法による構文解析法。 - 構文解析（Parsing）
入力が文法に従っているかを解析する処理。コンパイラの中核工程。 - 字句解析（Lexical Analysis）
ソースコードをトークンに分割する処理。通常は正規表現とDFAで実装。 - 正規表現
正規言語を記述する記法。grepやプログラムの入力検証で利用。 - コンパイラ
高級言語を機械語へ変換するソフトウェア。字句解析・構文解析・意味解析などの工程を持つ。
本問は「BNFの暗記問題」ではなく、
形式言語理論・オートマトン・数論・コンパイラ理論を
横断的に結び付けて理解しているかを確認する総合理解問題である。
この記事へのコメント