応用情報技術者 2017年秋期午前2 問02

問題文

次の BNF において非終端記号〈A〉から生成される文字列はどれか。　

⟨ R_{0} ⟩ ⟨ R_{1} ⟩ ⟨ R_{2} ⟩ ⟨ A ⟩ ⟨ B ⟩ ⟨ C ⟩ ::= 0 ∣ 3 ∣ 6 ∣ 9 ::= 1 ∣ 4 ∣ 7 ::= 2 ∣ 5 ∣ 8 ::= ⟨ R_{0} ⟩ ∣ ⟨ A ⟩ ⟨ R_{0} ⟩ ∣ ⟨ B ⟩ ⟨ R_{2} ⟩ ∣ ⟨ C ⟩ ⟨ R_{1} ⟩ ::= ⟨ R_{1} ⟩ ∣ ⟨ A ⟩ ⟨ R_{1} ⟩ ∣ ⟨ B ⟩ ⟨ R_{0} ⟩ ∣ ⟨ C ⟩ ⟨ R_{2} ⟩ ::= ⟨ R_{2} ⟩ ∣ ⟨ A ⟩ ⟨ R_{2} ⟩ ∣ ⟨ B ⟩ ⟨ R_{1} ⟩ ∣ ⟨ C ⟩ ⟨ R_{0} ⟩

🖊️ 解答を隠して解いてみる

選択肢

ア：123（正解）

イ：124

ウ：127

エ：128

🔒 解説は解答すると表示されます

BNF文字列導出【午前2解説】

正解の理由

選択肢ア（123）は、非終端記号〈A〉から規則をたどって生成可能です。具体的には規則列 A → A R0、A → B R2、B → R1 を適用すると、終端列として R1 R2 R0（すなわち 1 2 3）を得られます。各 R_i はそれぞれ {R0→{0,3,6,9}, R1→{1,4,7}, R2→{2,5,8}} の集合から任意の1つを選べるため、R1=1、R2=2、R0=3 とすれば 123 が生成されます。

（順序を誤る例：例えば A → C R1、C → A R2、A → R0 と展開すると終端列は R0 R2 R1、つまり 3 2 1 になり「123」にはならない点に注意してください。）

解法ステップ

目標文字列 1(=R1) 2(=R2) 3(=R0) のクラス配列は R1 R2 R0 であることを確認する。
〈A〉から出発して末尾が R0 となる規則を使う（A → A R0 または A → R0）。長さ3にするため A → A R0 を選ぶ。
左側の A を展開して残りを R1 R2 とする必要があるので A → B R2 を使う。
さらに B を R1 に展開（B → R1）すると、全体で (R1 R2) R0 が得られ、端的に R1 R2 R0 = 1 2 3 となる。
最後に各 Ri を具体的な数字で選ぶ（R1=1、R2=2、R0=3）。

展開の流れ（左導出の一例）： A ⇒ A R0 ⇒ (B R2) R0 ⇒ (R1 R2) R0 ⇒ 1 2 3

選択肢別の誤答解説

ア: 生成可能。上の導出で示した通り、A → A R0、A → B R2、B → R1 の適用により得られる。
イ（124 = R1 R2 R1）: 末尾が R1 なので A → C R1 を使う必要がある。すると C が先頭の 2 文字（R1 R2）を生成しなければならないが、C の規則から長さ2で先頭が R1 かつ末尾が R2 となる導出は作れない（C → A R2 の場合 A が単独で R1 を生成できない、C → B R1 は末尾が R1 になってしまう、C → C R0 は末尾が R0 ）。従って 124 は生成不可。
ウ（127 = R1 R2 R1）: 127 は 124 と同じクラス配列（R1 R2 R1）なので、同様に生成不可。
エ（128 = R1 R2 R2）: 末尾が R2 のため A → B R2 を選ぶ必要がある。すると B が先頭の 2 文字（R1 R2）を生成しなければならないが、B の規則で長さ2の文字列を R1 R2 にすることはできない（B → A R1 の場合末尾が R1、B → C R2 の場合 C が単独で R1 を作る必要があるが C は単独で R1 を生成できない、B → B R0 は末尾が R0）。従って 128 も生成不可。

よくある誤解

非終端の展開順を無視してしまい、非終端記号が「入れ替わって」しまうと誤った終端列順を得る（例：A→C R1, C→A R2, A→R0 は順序を誤ると 3 2 1 を与える）。
Ri の集合のどれか1つを選べば良いことを忘れ、Ri を特定の1字として固定できると思い込む（実際は各 Ri から任意の候補を選べる）。
「長さが同じだから生成可能」とだけ考え、生成規則の末尾記号クラス（R0/R1/R2）の整合性を確認しない。

補足コラム

この種の問題は「各位置の数字がどの Ri に属するか」を先に対応付けると解きやすくなります。まず候補文字列をクラス列（R1,R2,R0 等）に変換し、文法の各規則がそのクラス列をどのように分割・結合できるかを検討します。導出の際は左導出（左端から順に展開）か右導出を一貫して使うと順序ミスを防げます。

FAQ

Q: どうやって「生成不可」を数学的に示すべきですか？
A: まず末尾クラスに対応する〈A〉の適用規則（A→R0 / A→A R0 / A→B R2 / A→C R1）を調べ、必要となる部分列を生成できるかを規則ごとに反証します。可算有限個の規則なので各場合分けで不可能性を示せます。

Q: R_i の中からどの数字を選べば良いか迷ったら？
A: 生成可能性の判定はクラス（R0/R1/R2）だけで行い、具体的な数字は最後に任意に選べば良い（問題はクラスの順序・長さの整合性が鍵）。

関連キーワード: BNF、導出規則、左導出、非終端記号、生成可能性

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！