応用情報技術者 試験情報＆徹底解説

https://www.ap-siken.com/kakomon/29_aki/q2.html

BNF問題が理解できず苦しんでいます。
どうにか私のカチカチつるつるな脳みそにご助言を
お願いします。

例問として上述URLの問題ですが、
応用情報技術者平成29年秋期 午前問2

解き方として、まず回答選択肢をBNFに変換することは理解出来ます。

ア）123  ＝  <R1><R2><R0>
イ）124  ＝  <R1><R2><R1>
ウ）127  ＝  <R1><R2><R1>
エ）128  ＝  <R1><R2><R2>

BNFが重複しているイ、ウを答えから除外出来ることは理解できます。
ここから先の考え方がわかりません。
解説文の
------------------------------------------------
次に<A>の定義にある「<A><R0>」「<B><R2>」「<C><R1>」の3つの型から導出されるBNFのパターンを考えます。

[<A> <R0>]
非終端記号<A>に、それぞれ3つの型を当てはめます。
<A><R0><R0>→<R0><R0><R0>
<B><R2><R0>→<R1><R2><R0>
<C><R1><R0>→<R2><R1><R0>
…（省略）
------------------------------------------------
という部分が、どういう導き方をしているのかわかりません。

解説中「<A>の定義」とは、以下のことですね。
<A> ::= <R0>｜<A> <R0>｜<B> <R2>｜<C>< R1>

確かに<A>の定義の中に「<A><R0>」「<B><R2>」「<C><R1>」があることはわかります。
次に、<A>に3つの型を当てはめる、というところで頭に"？"が出てきます。

この解説は、定義の風呂敷をどんどん広げていき、表せるパターンを全て洗い出し、当てはまるものを見つけるやり方です。汎用的な解き方と言えますが、手間はかかります。

<A> ::= <R0>｜<A> <R0>｜<B> <R2>｜<C> <R1>
を見ると、
<A>は、
<R0>であれば1文字、
<A> <R0>であれば<A>の文字数＋1文字、
<B> <R2>であれば<B>の文字数＋1文字、
<C> <R1>であれば<C>の文字数＋1文字、
であり、
上記の<A>や<B>や<C>が1文字であれば、<A>は(<B>も<C>も)2文字になり、
上記の<A>や<B>や<C>が2文字であれば、<A>は(<B>も<C>も)3文字になり、
というように、無限に文字数が増えていきます。

ちょっと簡略化して書きます。

A＝R0 or AR0 or BR2 or CR1
ですが、選択肢はいずれも3文字ですから、このうちR0は省かれます。
A＝AR0 or BR2 or CR1
右辺のAに右辺を代入、右辺のBに問題文のBの定義の右3通りを代入、右辺のCに問題文のCの定義の右3通りを代入すると、
A＝(AR0 or BR2 or CR1)R0 or (AR1 or BR0 or CR2)R2 or (AR2 or BR1 or CR0)R1
＝AR0R0 or BR2R0 or CR1R0 or AR1R2 or BR0R2 or CR2R2 or AR2R1 or BR1R1 or CR0R1
ここで、右辺のAにR0、BにR1、CにR2を代入すると、
A＝R0R0R0 or R1R2R0 or R2R1R0 or R0R1R2 or R1R0R2 or R2R2R2 or R0R2R1 or B1R1R1 or R2R0R1
あとは、解説通りです。

ここで、私の解き方です。この問題に特化した解き方ですが、他の問題でも使えるかもしれません。

選択肢のそれぞれが正解、つまりAで定義できるなら、
アは、最後の3がR0だから、AR0の形式であり、そのAは上2桁の12
イは、最後の4がR1だから、CR1の形式であり、そのCは上2桁の12
ウは、最後の7がR1だから、CR1の形式であり、そのCは上2桁の12
エは、最後の8がR2だから、BR2の形式であり、そのBは上2桁の12
となります。
12がA、B、Cで定義できるかを考えると、
12の最初の1はR1(つまりB)、最後の2はR2だから、BR2はAでしか定義できず、アが正解

もっと早い解き方です。

選択肢3文字のうち、先頭2文字はいずでも12であり、12を定義できるのは、BR2を含むAだけです。

次に、Aの定義で、Aの次に来るのはR0であり、選択肢の最後の桁としてR0に該当するのは、3のアです。

TO：助け人さん
ご回答ありがとうございます。

> 無限に文字数が増えていきます。
そうですよね！
「再帰的に呼び出すから無限に増えるよな～」という
ところだけ頭にひっかかり、そこが問題の解説文で触れられておらず
思考停止してしまっていました。

後半のご説明も理解できました。
BNFの問題に取り組んで、慣れていきたいと思います！