フランスで正規言語をいじる

パリでの一年間の留学生活を綴る(かも)

正規言語の零壱則

たまには正規言語の研究の話を.今年パリで証明した定理について紹介します.

どのような定理かざっくりカジュアルに言うと

正規言語 Lが「ほとんど全ての文字列を含む」または「ほとんど全ての文字列を含まない」⇔  Lを受理する代数構造が零元を持つ ⇔   Lを受理する最小オートマトンが特別な形をしている

ということを示しました. 

「カジュアルに」と書いてみたものの,自分で読んでみてもなかなか意味不明です.もうちょっときっちりフォーマルに説明してみましょう. 

正規言語の零壱則

零壱則(zero-one law)とは,ある種の事象が「確率1で起こる(確実に起こる)」か「確率0で起こる(確実に起こらない)」という両極端な振る舞いを示す時に使われる言葉です.

零壱則という名前は一般的なもので,「XXXの零壱則(XXX's zero-one law)」という名前の定理や事実がWikipediaにはいくつか列挙されています.

Zero–one law - Wikipedia, the free encyclopedia 

It may refer to:

 

今回紹介するのは「正規言語の零壱則」です.有限の文字集合を Aとし, A上の全ての有限長文字列の集合を A^*で,長さ n全ての文字列の集合を A^nで表します. A上の正規言語 L \subseteq A^*に対して確率関数 \mu_n(L)を次のように定義します:

\begin{align} \displaystyle \mu_n(L) = \frac{|L \cap A^n|}{|A^n|} = \frac{|L \cap A^n|}{|A|^n}. \end{align}

この関数 \mu_n(L)は「長さnの文字列集合 A^nからランダムに取ってきた文字列 w \in A^n Lに属している確率」を表していることが分かります. 

さて,ある正規言語 Lについて,上で定義した確率関数の極限が0か1に収束するとき,つまり \lim_{n \rightarrow \infty}\mu_n(L) \in \{0,1\}のとき,正規言語 Lは零壱則に従うと呼ぶことにしましょう.直感的には正規言語 Lが零壱則を満たすとは Lが「ほとんど全ての文字列を含む」または「ほとんど全ての文字列を含まない」と考えることができます. 

零壱則の決定可能性について

さてさて,ここで定義した正規言語の零壱則は決定可能な性質,つまり「与えられた正規言語 Lが零壱則に従うかどうか」を判定するアルゴリズムはあるのでしょうか? いかにもありそうです.実際それを求めたのが今回の定理なのですが,それを説明するためにもうちょっと用語を整理する必要があります.

統語半群

正規言語が(決定性)有限オートマトンで特徴付けられることは広く知られています.(この辺が良くわからないという人は拙著『正規表現技術入門』をどうぞ :-) 

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

 

一方, 正規言語が有限モノイドでも特徴付けられるということはあまり知られていません(この代数的特徴付けも『正規表現技術入門』の巻末付録にて解説されています).

モノイドとは結合則を満たす二項演算と単位元を持った代数構造で,群から「逆元の条件」を取り払ったモノです.例えば文字列の集合 A^*も「2つの文字列を結合して1つの文字列にする操作」を二項演算として考えるとモノイド構造が入ります.この場合の単位元は空文字列です.

さて,正規言語Lから有限オートマトンを具体的に構成することができるように,言語LからLに対応する特別なモノイド -- 統語半群(syntactic monoid)*1   M を次のように構成することができます:

\begin{align} M = A^* / \sim_L. \end{align}

ここで \sim_Lは言語 Lによって定まる A^*上の同値関係:

\begin{align} u \sim_L v \Leftrightarrow \forall x,y \in A^* [ xuy \in L \Leftrightarrow xvy \in L ]  \end{align}

で,  A^* / \sim_L は文字列の集合(無限モノイド) A^* \sim_Lで割ったモノイドです.有名なMyhill-Nerodeの定理は言語 Lの正規性をこの統語半群 A^*/\sim_Lの有限性で特徴付ける綺麗な定理です.

定理(Myhill-Nerode)

言語 Lが正規 ⇔  Lの統語半群が有限.

 

 さて,これで正規言語の零壱則について説明する道具が駆け足ながら揃いました.

主定理 

定理1(正規言語の零壱則)

正規言語 Lについて以下の3つの条件は等しい: 

  1.  Lが零壱則に従う
  2.  Lの統語半群が零元を持つ
  3.  Lの最小オートマトンが零オートマトン

ここで言うモノイドの M零元とは,次の条件を満たす Mのある元 xのことです:

\begin{align} \forall m \in M [xm = mx = x]. \end{align}

例えば整数と掛け算の成すモノイドは数の 0が零元となります. 0には何を掛けても 0,そのまんまですね.

確率関数  \mu_n(L)の極限が0か1に収束するという条件(1)と統語半群に零元が存在するという条件(2)とが同値というのが意外かもしれません.条件(2)から条件(1)を示すのは容易なのですが,その逆を示すのがなかなか難しいです.

実際の証明では条件(3)の零壱則のオートマトン的特徴付け(零オートマトン)をうまく活用して「条件(2)⇒条件(3)⇒条件(1)」を示しました(零オートマトンの定義はちょっとややこしいので割愛します).条件(3)から条件(1)を示すのが証明の一番面白いところで,零壱則を満たす言語族の閉包性とEilenbergによる正規言語のVariety Theoremの核となる補題を...... 証明の詳細はGandALF'15という国際会議に採択された拙文"An Automata Theoretic Approach to the Zero-One Law for Regular Languages: Algorithmic and Logical Aspects"にてご確認ください.

EPTCS: An Automata Theoretic Approach to the Zero-One Law for Regular Languages: Algorithmic and Logical Aspects

統語半群 A^*/\sim_Lは正規言語 Lから具体的に構成でき,零元があるかどうかも判定することができるため,定理1は正規言語の零壱則が決定可能な性質であることを導きます.

有限グラフの零壱則 

そもそも零壱則に興味を持ったのは,去年輪講*2した"Elements of Finite Model Theory"に載っていた有限グラフ零壱則を特徴づけるFaginの定理がきっかけでした.

定理(Fagin) 

一階述語論理式 \phiがほとんど全ての有限グラフで成り立つ(i.e.  \lim_{n \rightarrow \infty} \mu_n(\phi) = 1) ⇔  \phiがランダムグラフで成り立つ.

ここでいうランダムグラフとはある特別な無限グラフです.ランダムグラフはいくつかの異なる,しかし等価な構成法がしられており,構成法の提案者の名前を取ってErdős–RényiグラフRadoグラフとも呼ばれたりします.

このFaginの定理は有限グラフの零壱則の決定可能な特徴付けにもなっています.このFaginの定理のように綺麗な定理が有限文字列の零壱則 -- すなわち正規言語の零壱則でも成り立たないか?と考えるのは自然なことのように思えます.

有限グラフの零壱則とFaginの定理,正規言語と論理の関係について詳しく知りたい!という人はぜひ Elements of Finite Model Theory を読むことをお勧めします.僕は論理やモデル理論の知識が全くない状態からこの書籍を輪講しましたが,説明が丁寧で飛躍が無くとてもわかり易かったです.有限モデル理論の良い入門書だと思います*3

Elements of Finite Model Theory (Texts in Theoretical Computer Science. An EATCS Series)

Elements of Finite Model Theory (Texts in Theoretical Computer Science. An EATCS Series)

 

 

 

 

*1:syntactic monoid を素直に訳すと「統語的モノイド」あるいは「統語的単位半群」になりますが,本記事では超大胆に縮めて「統語半群」と呼ぶことにします.これは一般的な訳語ではありません.というかそもそもsyntactic moniodを日本語に訳している文献の数はとても少ない.

*2:輪講に付き合ってくれた東工大の同期の松田くんと後輩の中村君に感謝

*3:嬉しい事に著者のLibkin先生が原稿をPDFで公開してくれています.