帰納的定義と証明技法 文字列に関する構造帰納法 文字列の帰納的定義 BNF(Backus Naur Format)、自然数
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第3章(帰納的定義と証明技法)、3.3(文字列に関する構造帰納法)、3.3.1(文字列の帰納的定義)の問3.8の解答を求めてみる。
<零> ::= 0
<零以外> ::= 1|2|3|4|5|6|7|8|9
<数字> ::= <零>|<零以外>
<数字の並び> ::= <数字>|<数字の並び><数字>
<自然数> ::= <数字>|<零以外><数字の並び>