お絵描きで学ぶ・無限正規ツリーとBNF(バッカス／ナウア形式) - 檜山正幸のキマイラ飼育記 (はてなBlog)

久々のお絵描き講座です。10枚の絵を描いたぞ（って、落描きみたいなモンですけど）。 有向グラフは計算科学（コンピューティング・サイエンス）で頻出する大事なデータ構造です。コンピュータで扱えるのは有限グラフですが、無限グラフが登場しないのかというと、そうではありません。コンピュータでも、可能性として無限となりうるデータ構造を扱います。とはいえ、何の秩序もない無限データはさすがに扱いにくいので、有限的に定義できる無限構造が興味の対象となります。 ここでは、無限な有向グラフのなかで最もよく使う無限ツリーを考えます。さらに、次の条件を満たすものを例題に使います。 末端のノード（リーフノード）には整数の値が付着している。 中間の分岐ノードは特に値を持たない。 絵を描くときは、末端ノードには単に整数だけを書き、中間ノードは黒丸にします。ルートノードを識別するためには、「ルート」とラベルを書いた矢印を使