前回から、応用情報技術者試験(AP)平成26年春期 午前問3に出題された「BNF(バッカス・ナウア記法)」の問題を解いています。まだ解いてないけど。
この問題は、
非終端記号<A>から生成される文字列はどれか。
ア 123 イ 124 ウ 127 エ 128
ということですから、言い換えると、
非終端記号<A>を使って表現可能な文字列はどれか。
ア 123 イ 124 ウ 127 エ 128
とも考えられます。
<A>の定義は、
<A> ::= <R0> | <A><R0> | <B><R2> | <C><R1>
で、::=はイコールみたいなものだと考えると、
<R0> か <A><R0> か <B><R2> か <C><R1>
で
123 か 124 か 127 か 128
のいずれも3文字の文字列のうち表せるものはどれか、と考えることもできます。
(1)<R0>
上記のうち、<R0>について考えてみます。
<R0>は
<R0> ::= 0 | 3 | 6 | 9
ですので、<R0>では、
0 か 3 か 6 か 9
という1文字しか表せません。さすがにこれは見て見ぬふりは出来ません。したがって可能性があるのは、
<A><R0> か <B><R2> か <C><R1>
のいずれかということになります。
(2)<A><R0>
そこで次に、<A><R0>について考えてみます。
ここで、
<A> ::= <A><R0>
って何？ 何で<A>が両方にいるの？
となると、白雲斎の術中にはまってしまいますので、右辺だけに注目して、右辺の<A>を
<R0> | <A><R0> | <B><R2> | <C><R1>
のいずれかに置き換えてみます。
ということで、
<A>
↓
<A><R0>
↓
①<R0><R0>
②<A><R0><R0>
③<B><R2><R0>
④<C><R1><R0>
を表現できることがわかります。
(3)<R0><R0>
ただし、
①<R0><R0>
では、
00、03、06、09
30、33、36、39
60、63、66、69
90、93、96、99
という２文字の文字列しか表せません。
目的は3文字ですので、これは違います。
そこで、
②<A><R0><R0>
③<B><R2><R0>
④<C><R1><R0>
をさらに展開させて考えることにします。
(4)<A><R0><R0>
次に、②<A><R0><R0>について考えてみます。今回も右辺の<A>を
<R0> | <A><R0> | <B><R2> | <C><R1>
のいずれかに置き換えてみます。
ということで、
<A>
↓
<A><R0>
↓
②<A><R0><R0>
↓
⑤<R0><R0><R0>
⑥<A><R0><R0><R0>
⑦<B><R2><R0><R0>
⑧<C><R1><R0><R0>
を表現できることがわかります。
(5)<R0><R0><R0>
ここで、
⑤<R0><R0><R0>
で表せる文字列を考えてみると、
<R0>は、0 か 3 か 6 か 9
ですので、以下を表すことができます。
000、003、006、009
030、033、036、039
060、063、066、069
090、093、096、099
300、303、306、309
330、333、336、339
360、363、366、369
390、393、396、399
600、603、606、609
630、633、636、639
660、663、666、669
690、693、696、699
900、903、906、909
930、933、936、939
960、963、966、969
990、993、996、999
残念ながら、
ア 123 イ 124 ウ 127 エ 128
はいずれも出てきませんでしたが、3文字の文字列を表すことには成功しました。
他の
⑥<A><R0><R0><R0>
⑦<B><R2><R0><R0>
⑧<C><R1><R0><R0>
は、4文字以上になってしまいますので、考える必要はなさそうです。
(6)<B><R2><R0>
次に、③<B><R2><R0>について考えてみます。右辺の<B>を
<R1> | <A><R1> | <B><R0> | <C><R2>
のいずれかに置き換えてみようかと思いましたが、3文字になるのは<R1>だけですので、<R1>に置き換えてみます。
<R1>は::= 1 | 4 | 7
<R2>は::= 2 | 5 | 8
ですので、
ア 123 イ 124 ウ 127 エ 128
の"12"の部分を表すことができます。
そうすると、
<R1><R2><R0>
で、
<R0>は::= 0 | 3 | 6 | 9
を表せますので、
ア 123
が、
非終端記号<A>を使って表現可能な文字列
ということになります。
非常に偶然行き着いた感が強いのですが
、記号の意味や賢い考え方はネットや参考書で賢者の皆様が解説されているので、そちらをご覧ください。
ただ頑張れば、
12→<R1><R2>→<B><R2>→<A><R0>
と行きつけるかもしれません。
****
記載ミスなどがありそうですので、今後しれっと直します。
今回は「次のBNFにおいて非終端記号<A>から生成される文字列はどれか」という問題を解いてみました。
