『かじる』というより，『なめる』，いや，『遠くから眺めた』程度の話。
BNF記法（BNF は Backus-Naur Form の略で，Backus と Naur はそれぞれ人名である）は，何らかの文字列を生成する規則の表し方である。
<word>::=a|b
と書いてあったら，<word> というのは a または b である，という意味である。
これだけだと大して面白くないが，次のような再帰的な定義が使えるところが奥の深いところのようだ。
<string>::=ab|a<string>b
と書かれていた場合，この導出規則で生成される文字列<string>は，次のうちどれだろうか？
BNF記法について初めて聞いた人にはこんな問題解けるわけがないだろうが，少し落ち着いて考えてみて欲しい。
この5つの文字列の特徴はなんだろうか？
おおまかに捕らえてみると，どの文字列も a から始まっている。
また，2 だけが最後に a がきており，よく見ると 5 だけ文字 c が使われている。
消去法で考えてみよう。
この段階で脱落するのはどれだろうか？
まず，<string>の導出規則には a と b という文字は出てくるが，c は出てこない。
だから c という，規則にない文字を使っている 5 が真っ先に駄目だとわかる。
次に2について検討しよう。果たして語尾に文字 a が来ることは可能だろうか？
導出規則を見てみると，<string> というのは，ab という文字列か，あるいはすでに出てきた<string>の頭に a を，末尾に b を追加した a(なんとか)b という形の文字列だということだから，いずれにしても，末尾は b しか出てこない。
したがって，末尾が a である 2 は<string>としては現れないことになる。
ところで，<string>は，ab そのものか，すでに生成された<string>に a と b を1つずつ追加して作られるわけだから，<string>には，常に文字 a と b が同じ数だけ含まれているのではないか，ということに気がつかないだろうか。
これを『証明』するとしたら，どうすればいいだろうか。
厳密な証明を述べるのは少々難しいような気がするが，数学的帰納法と同じ形式で証明できるように思うので，アイデアだけを記しておこう。
導出規則から，<string>に含まれるのは a か b のどちらかの文字だけのように思われる（さっき，さも当たり前のように 5 はあり得ないと断定したが，このことを『証明』しろといわれたら，どうしたらいいのかよくわからない）。
それが正しいとすると，<string>の導出規則から，<string>は必ず a と b を少なくとも1文字ずつ持つことがわかるので，文字列 ab が文字数が最小の<string>であることになる。
そして文字列 ab は a と b の個数が同数である。
また，ある<string>について，a と b が同数しか含まれていなければ，その先頭と末尾にそれぞれ a と b を付け加えて得られる新しい<string>にも a と b は同数含まれることになる。
したがって，導出規則に従って生み出されるどの<string>も，a と b を同数含むことになるはずである。
さて，この観点からも改めて 2 が駄目だとわかるが，新たに 3 も脱落することがわかる。
その結果，1 と 4 の一騎打ちとなる。
もし 1 が<string>だとすれば，ababab は ab とは異なるから，a<string>b の形の文字列だということになる。そこで両側の a と b をはがした残りの baba もまた<string>だということになるが，これは末尾が a であるため，<string>の資格を持たない。
よって 4 の aaabbb だけが<string>ではないか，ということになる。
実際に<string>としてこの文字列が現れ得るかを最後に検証してみよう。
手元に，<string>をいっぱい入れられるおもちゃ箱があるところを想像して欲しい。
最初，その箱は空っぽであるとして，<string>の導出手続きを繰り返して，出来た<string>をどんどん箱に入れていくことにする。
まず初代の<string>は，まだ手元に<string>が手元にないので，a<string>b の方の規則を当てはめるための『タネ』がないため，ab を採用するしかない。
これでおもちゃ箱には ab がチャリンと入る。
導出規則の適用の2回目は，すでに ab は獲得したから，これを<string>の種にして a<string>b を適用して得られる aabb を新しい<string>としてチャリンと箱に入れる。
3回目は，箱の中に ab と aabb があるわけだが，ab を使ってもさっき手に入れた aabb がまた出来るだけなので，それはもう持っているから aabb に a<string>b を適用して aaabbb をゲットする。
それもおもちゃ箱にチャリンと入れる。
ところで，この aaabbb は 4 の文字列に他ならないから，aaabbb は与えられた導出規則で生成される<string>のひとつであることが判明した。
ようやく一件落着である。なんだか文章が長くなってしまったが，詳しい解説を書いてみたかったので，まあ致し方ない。
なお，ネットで BNF記法について検索したら，大学の講義ノートらしき文書が見つかった。
それには練習問題がいくつか載っているが，そのうちのひとつに，10進表記の正の整数を全て生成するような導出規則を考えよという問題があった。これはかなり面白そうなパズルである。もちろん，先頭の位に 0 がくるような表記は除外せよということなので，よく考える必要がありそうだ。
それと関連して，漢数字による正の整数の表記を生成する導出規則を考えよという問題を思いついた。
このテーマは，僕が学部1年生のころに受けた講義のレポートにあったので思い出したのである。
その講義でBNF記法を習った覚えはないが，単に僕が覚えていないだけなのかもしれない。
普段よく使っている規則は，百と千は二百や七千とは違い，頭に『一』をつけないが，万より大きい単位では頭に一をつけて『一万』や『一億』とするので，このあたりの規則の違いをうまく表現するのは工夫が必要そうである。
しかし，漢数字を漢字で表現するのはまだ簡単そうだが，数字の「読み」を生成するのはさらにややこしそうである。こちらが僕が受けた授業で出された課題だった。
『さんびゃく』『さんぜん』や，『ろっぴゃく』『ろくせん』のように，他の数字のときとは異なる音便になったり，数字のあとにくる単位によって数字の読みが変わったりと，規則はより複雑になるので大変そうである。
ともかく，BNF記法，あるいは関連の話題というのは面白そうである。
ほんの入門程度の内容であっても，頭の体操にもってこいである。
BNF記法（BNF は Backus-Naur Form の略で，Backus と Naur はそれぞれ人名である）は，何らかの文字列を生成する規則の表し方である。
<word>::=a|b
と書いてあったら，<word> というのは a または b である，という意味である。
これだけだと大して面白くないが，次のような再帰的な定義が使えるところが奥の深いところのようだ。
<string>::=ab|a<string>b
と書かれていた場合，この導出規則で生成される文字列<string>は，次のうちどれだろうか？
- ababab
- abbbba
- abbbab
- aaabbb
- aaacbb
BNF記法について初めて聞いた人にはこんな問題解けるわけがないだろうが，少し落ち着いて考えてみて欲しい。
この5つの文字列の特徴はなんだろうか？
おおまかに捕らえてみると，どの文字列も a から始まっている。
また，2 だけが最後に a がきており，よく見ると 5 だけ文字 c が使われている。
消去法で考えてみよう。
この段階で脱落するのはどれだろうか？
まず，<string>の導出規則には a と b という文字は出てくるが，c は出てこない。
だから c という，規則にない文字を使っている 5 が真っ先に駄目だとわかる。
次に2について検討しよう。果たして語尾に文字 a が来ることは可能だろうか？
導出規則を見てみると，<string> というのは，ab という文字列か，あるいはすでに出てきた<string>の頭に a を，末尾に b を追加した a(なんとか)b という形の文字列だということだから，いずれにしても，末尾は b しか出てこない。
したがって，末尾が a である 2 は<string>としては現れないことになる。
ところで，<string>は，ab そのものか，すでに生成された<string>に a と b を1つずつ追加して作られるわけだから，<string>には，常に文字 a と b が同じ数だけ含まれているのではないか，ということに気がつかないだろうか。
これを『証明』するとしたら，どうすればいいだろうか。
厳密な証明を述べるのは少々難しいような気がするが，数学的帰納法と同じ形式で証明できるように思うので，アイデアだけを記しておこう。
導出規則から，<string>に含まれるのは a か b のどちらかの文字だけのように思われる（さっき，さも当たり前のように 5 はあり得ないと断定したが，このことを『証明』しろといわれたら，どうしたらいいのかよくわからない）。
それが正しいとすると，<string>の導出規則から，<string>は必ず a と b を少なくとも1文字ずつ持つことがわかるので，文字列 ab が文字数が最小の<string>であることになる。
そして文字列 ab は a と b の個数が同数である。
また，ある<string>について，a と b が同数しか含まれていなければ，その先頭と末尾にそれぞれ a と b を付け加えて得られる新しい<string>にも a と b は同数含まれることになる。
したがって，導出規則に従って生み出されるどの<string>も，a と b を同数含むことになるはずである。
さて，この観点からも改めて 2 が駄目だとわかるが，新たに 3 も脱落することがわかる。
その結果，1 と 4 の一騎打ちとなる。
もし 1 が<string>だとすれば，ababab は ab とは異なるから，a<string>b の形の文字列だということになる。そこで両側の a と b をはがした残りの baba もまた<string>だということになるが，これは末尾が a であるため，<string>の資格を持たない。
よって 4 の aaabbb だけが<string>ではないか，ということになる。
実際に<string>としてこの文字列が現れ得るかを最後に検証してみよう。
手元に，<string>をいっぱい入れられるおもちゃ箱があるところを想像して欲しい。
最初，その箱は空っぽであるとして，<string>の導出手続きを繰り返して，出来た<string>をどんどん箱に入れていくことにする。
まず初代の<string>は，まだ手元に<string>が手元にないので，a<string>b の方の規則を当てはめるための『タネ』がないため，ab を採用するしかない。
これでおもちゃ箱には ab がチャリンと入る。
導出規則の適用の2回目は，すでに ab は獲得したから，これを<string>の種にして a<string>b を適用して得られる aabb を新しい<string>としてチャリンと箱に入れる。
3回目は，箱の中に ab と aabb があるわけだが，ab を使ってもさっき手に入れた aabb がまた出来るだけなので，それはもう持っているから aabb に a<string>b を適用して aaabbb をゲットする。
それもおもちゃ箱にチャリンと入れる。
ところで，この aaabbb は 4 の文字列に他ならないから，aaabbb は与えられた導出規則で生成される<string>のひとつであることが判明した。
ようやく一件落着である。なんだか文章が長くなってしまったが，詳しい解説を書いてみたかったので，まあ致し方ない。
なお，ネットで BNF記法について検索したら，大学の講義ノートらしき文書が見つかった。
それには練習問題がいくつか載っているが，そのうちのひとつに，10進表記の正の整数を全て生成するような導出規則を考えよという問題があった。これはかなり面白そうなパズルである。もちろん，先頭の位に 0 がくるような表記は除外せよということなので，よく考える必要がありそうだ。
それと関連して，漢数字による正の整数の表記を生成する導出規則を考えよという問題を思いついた。
このテーマは，僕が学部1年生のころに受けた講義のレポートにあったので思い出したのである。
その講義でBNF記法を習った覚えはないが，単に僕が覚えていないだけなのかもしれない。
普段よく使っている規則は，百と千は二百や七千とは違い，頭に『一』をつけないが，万より大きい単位では頭に一をつけて『一万』や『一億』とするので，このあたりの規則の違いをうまく表現するのは工夫が必要そうである。
しかし，漢数字を漢字で表現するのはまだ簡単そうだが，数字の「読み」を生成するのはさらにややこしそうである。こちらが僕が受けた授業で出された課題だった。
『さんびゃく』『さんぜん』や，『ろっぴゃく』『ろくせん』のように，他の数字のときとは異なる音便になったり，数字のあとにくる単位によって数字の読みが変わったりと，規則はより複雑になるので大変そうである。
ともかく，BNF記法，あるいは関連の話題というのは面白そうである。
ほんの入門程度の内容であっても，頭の体操にもってこいである。
