このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

お絵描きで学ぶ・無限正規ツリーとBNF(バッカス/ナウア形式)

久々のお絵描き講座です。10枚の絵を描いたぞ(って、落描きみたいなモンですけど)。

有向グラフは計算科学(コンピューティング・サイエンス)で頻出する大事なデータ構造です。コンピュータで扱えるのは有限グラフですが、無限グラフが登場しないのかというと、そうではありません。コンピュータでも、可能性として無限となりうるデータ構造を扱います。とはいえ、何の秩序もない無限データはさすがに扱いにくいので、有限的に定義できる無限構造が興味の対象となります。

ここでは、無限な有向グラフのなかで最もよく使う無限ツリーを考えます。さらに、次の条件を満たすものを例題に使います。

  1. 末端のノード(リーフノード)には整数の値が付着している。
  2. 中間の分岐ノードは特に値を持たない。

絵を描くときは、末端ノードには単に整数だけを書き、中間ノードは黒丸にします。ルートノードを識別するためには、「ルート」とラベルを書いた矢印を使います。次は、有限ツリーを描いた例です。

ツリーの描き方

無限二分木

次の図のような無限に続く二分木を考えます。この無限二分木には末端ノードはなくて、すべてのノードが中間ノードです。中間ノードが無限に続きます。

無限二分木

ツリー全体やサブツリーを、A, B,C などの英字大文字で表すことにします。次のような感じです。

ツリーとサブツリーを記号で表す

この図とまったく同じことを、テキスト記法では次のように表現しましょう。


A ::= ・(B, C)

これはBNF(バッカス/ナウア形式)の一種です。タプル (B, C) の前に付いている黒丸「・」は、図の「BとCを接合する黒丸」に対応していると思ってください。

今話題にしている無限二分木では、AとBとCが同じ形状のツリーなので、そのBNFは次のように書けます。


A ::= ・(A, A)

定義式の左辺にも左辺にもAが登場するので、これは再帰的な定義です。再帰的な定義は、「可能性としての無限」を導入します。

また、再帰的な無限構造は循環的構造による表現が可能です。無限二分木は、次のような循環的グラフ(サイクルを持つ有向グラフ)で有限的に表すことができます。無限構造だけど「有限的な表現」を持つ点がキモです。

無限二分木を表現する循環的グラフ

BNFなり循環的グラフなりの有限的な表現を持つ無限ツリーは正規ツリー(regular tree)とか有理ツリー(rational tree)とか呼ばれます。「正規」は正規表現の「正規」です。実際、ツリーがBNFで定義できることは(ツリー用の)正規表現で定義できることと同じです。「有理」は有理数の「有理」と同じです。有理数は少数展開すると無限小数になるかも知れないけど、分数で有限的に表現できるわけで、よく似た概念でしょ。

末端ノードを持つ無限三分木

今度は次の無限ツリーを考えましょう。

末端ノードを持つ無限三分木

中間ノードから枝が3本出ますが、真ん中の枝は整数3が付着した末端ノードに繋がり終端します。左右の枝は無限に伸びます。

もうあまり説明は要らないでしょう。この無限三分木のBNFは次のとおり。


A ::= ・(A, 3, A)

対応する循環的グラフはこうなります。

末端ノードを持つ無限三分木を表現する循環的グラフ

無限に続くリスト

次なる例は下図のものです。

無限に続くリスト

これをLispSchemeのリストだと思うと、整数値2が無限に並んだリストになります。終端のnilは出てきません(無限の彼方にnilがあると思ってもいいです)。


(2 2 2 2 2 ...)

これのBNFはもはや明らかですね。


A ::= ・(2, A)

対応する循環的グラフも簡単。

無限に続くリストを表現する循環的グラフ

これはどんな無限ツリー?

最後の例はBNFからスタートします。


A ::= ・(2, B)
B ::= ・(A, 3)

これは、AとBが相互再帰している再帰的定義です。AとBをそれぞれ独立したツリーとして絵を描くと次のようです。

2つのツリー

これを繋ぎ合わせて1つの循環的グラフを作るには多少の慣れが必要かも知れません。Aのルートを全体のルートにして、Bをその下にぶら下げることにします。すると、結果の循環的グラフは次のようです。

2つのツリーを繋ぎ合わせた循環的グラフ

循環的グラフを無限ツリーに展開するのは宿題にしましょう。どんな無限ツリーになるかな?


僕はこういう絵を描くのがほんとに好きなんだけど、スキャンしたり切った張ったが手間なんですよねぇ。頭のなかでは絵図で考えていても、いつもは手からテキスト表現に翻訳している感じ。ブレインスキャンで絵が出てきたりするといいんだけど、、、