応用情報技術者 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、導出規則、左導出、非終端記号、生成可能性

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！