正規言語の零壱則
たまには正規言語の研究の話を.今年パリで証明した定理について紹介します.
どのような定理かざっくりカジュアルに言うと
正規言語が「ほとんど全ての文字列を含む」または「ほとんど全ての文字列を含まない」⇔ を受理する代数構造が零元を持つ ⇔ を受理する最小オートマトンが特別な形をしている
ということを示しました.
「カジュアルに」と書いてみたものの,自分で読んでみてもなかなか意味不明です.もうちょっときっちりフォーマルに説明してみましょう.
正規言語の零壱則
零壱則(zero-one law)とは,ある種の事象が「確率1で起こる(確実に起こる)」か「確率0で起こる(確実に起こらない)」という両極端な振る舞いを示す時に使われる言葉です.
零壱則という名前は一般的なもので,「XXXの零壱則(XXX's zero-one law)」という名前の定理や事実がWikipediaにはいくつか列挙されています.
Zero–one law - Wikipedia, the free encyclopedia
It may refer to:
- Borel–Cantelli lemma
- Blumenthal's zero–one law for Markov processes,
- Engelbert–Schmidt zero–one law for continuous, nondecreasing additive functionals of Brownian motion,
- Hewitt–Savage zero–one law for exchangeable sequences,
- Kolmogorov's zero–one law for the tail σ-algebra,
- Lévy's zero–one law, related to martingale convergence.
- topological zero–one law related to meager sets
今回紹介するのは「正規言語の零壱則」です.有限の文字集合をとし,上の全ての有限長文字列の集合をで,長さ全ての文字列の集合をで表します.上の正規言語に対して確率関数を次のように定義します:
\begin{align} \displaystyle \mu_n(L) = \frac{|L \cap A^n|}{|A^n|} = \frac{|L \cap A^n|}{|A|^n}. \end{align}
この関数は「長さnの文字列集合からランダムに取ってきた文字列がに属している確率」を表していることが分かります.
さて,ある正規言語について,上で定義した確率関数の極限が0か1に収束するとき,つまりのとき,正規言語は零壱則に従うと呼ぶことにしましょう.直感的には正規言語が零壱則を満たすとはが「ほとんど全ての文字列を含む」または「ほとんど全ての文字列を含まない」と考えることができます.
零壱則の決定可能性について
さてさて,ここで定義した正規言語の零壱則は決定可能な性質,つまり「与えられた正規言語が零壱則に従うかどうか」を判定するアルゴリズムはあるのでしょうか? いかにもありそうです.実際それを求めたのが今回の定理なのですが,それを説明するためにもうちょっと用語を整理する必要があります.
統語半群
正規言語が(決定性)有限オートマトンで特徴付けられることは広く知られています.(この辺が良くわからないという人は拙著『正規表現技術入門』をどうぞ :-)
正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)
- 作者: 新屋良磨,鈴木勇介,高田謙
- 出版社/メーカー: 技術評論社
- 発売日: 2015/04/14
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
一方, 正規言語が有限モノイドでも特徴付けられるということはあまり知られていません(この代数的特徴付けも『正規表現技術入門』の巻末付録にて解説されています).
モノイドとは結合則を満たす二項演算と単位元を持った代数構造で,群から「逆元の条件」を取り払ったモノです.例えば文字列の集合も「2つの文字列を結合して1つの文字列にする操作」を二項演算として考えるとモノイド構造が入ります.この場合の単位元は空文字列です.
さて,正規言語Lから有限オートマトンを具体的に構成することができるように,言語LからLに対応する特別なモノイド -- 統語半群(syntactic monoid)*1 を次のように構成することができます:
\begin{align} M = A^* / \sim_L. \end{align}
ここでは言語によって定まる上の同値関係:
\begin{align} u \sim_L v \Leftrightarrow \forall x,y \in A^* [ xuy \in L \Leftrightarrow xvy \in L ] \end{align}
で, は文字列の集合(無限モノイド)をで割ったモノイドです.有名なMyhill-Nerodeの定理は言語の正規性をこの統語半群の有限性で特徴付ける綺麗な定理です.
定理(Myhill-Nerode)
言語が正規 ⇔ の統語半群が有限.
さて,これで正規言語の零壱則について説明する道具が駆け足ながら揃いました.
主定理
定理1(正規言語の零壱則)
正規言語について以下の3つの条件は等しい:
- が零壱則に従う
- の統語半群が零元を持つ
- の最小オートマトンが零オートマトン
ここで言うモノイドのの零元とは,次の条件を満たすのある元のことです:
\begin{align} \forall m \in M [xm = mx = x]. \end{align}
例えば整数と掛け算の成すモノイドは数のが零元となります.には何を掛けても,そのまんまですね.
確率関数 の極限が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"にてご確認ください.
今年パリで示した定理の論文がGandALF'15に採択されました. 「正規言語Lがほとんど全ての文字列を含む/含まない(零壱則に従う) ⇔ Lのsyntactic monoidが零元を持つ」というカッコいい定理(私見)です. http://t.co/dUID7MyzSP
— Ryoma Sin'ya (@sinya8282) 2015, 8月 8
統語半群は正規言語から具体的に構成でき,零元があるかどうかも判定することができるため,定理1は正規言語の零壱則が決定可能な性質であることを導きます.
有限グラフの零壱則
そもそも零壱則に興味を持ったのは,去年輪講*2した"Elements of Finite Model Theory"に載っていた有限グラフ零壱則を特徴づけるFaginの定理がきっかけでした.
定理(Fagin)
一階述語論理式がほとんど全ての有限グラフで成り立つ(i.e. ) ⇔ がランダムグラフで成り立つ.
ここでいうランダムグラフとはある特別な無限グラフです.ランダムグラフはいくつかの異なる,しかし等価な構成法がしられており,構成法の提案者の名前を取って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)
- 作者: Leonid Libkin
- 出版社/メーカー: Springer
- 発売日: 2004/07/02
- メディア: ハードカバー
- この商品を含むブログを見る
SOLDES(ソルドゥ)でお得なお買い物:万年筆を購入
フランスに来て9ヶ月が過ぎましたが.まだまだこの国がよく分からなくて面白いです.
法律で定められたセール期間
フランスでは夏と冬にそれぞれ5週間ほどバーゲンセール"Soldes"が行われます.なんでも,このSoldes期間外では店は大幅な値下げをしてモノを売ることができないそうです(なんだそりゃ).面白いですね.
年2回のショッピングチャンス 「ソルド」
フランスでは夏と冬の年2回、所定の期間のみ行われるバーゲン「ソルドSoldes」があり、フランス人はこの時とばかりに目をつけていた品物をゲットします。有名ブランドのブティックなどでは初日の開店前から長い行列ができ、彼ら&彼女らの意気込みがうかがえます。もちろん観光客もこれを逃すことはありません。
ソルドについては期間、表示方法、宣伝の仕方などが法律で厳密に定められています。期間
- 「ソルド」と表示できるのは夏・冬各5週間の決まった日にちに実施されるバーゲンのみ。他の期間のバーゲンは「プロモーション」などとよばれます。
- 夏のソルドは6月の最終水曜日(それが28日よりあとなら最後から2番目の水曜日)午前8時から5週間。冬のソルドは1月の第2水曜日(それが12日よりあとなら第1水曜日)午前8時から5週間。フランスの海外県・海外地方でもソルドは実施されますが、気候や季節の違いからか、やはり本土とは大きく異なる日程になることがあります。
色んなモノが20~70%引きに
もちろん全部が全部セールの対象になるわけではありません.大きめのデパートやショッピング街に出て足を使ってお目当ての品を探すのが大事です.
ちなみに僕はマレ地区にあるデパート「LE BHV MARAIS」でS.T. Dupontの万年筆を50% off でゲットしました.
LE BHV MARAIS - Le style comme style de vie
万年筆
せっかくフランスにいるのでフランス製の万年筆を買おうと思い,S.T. Dupontの「Liberté」を買いました.定価400€の所を50% off の200€で!それでも高いですが,万年筆は末永く付き合うものなので良い買い物をしたと思っています.
ちなみにパリで面倒を見てもらってるJacques Sakarovitch先生の影響で僕も万年筆を使うようになりました.この万年筆でこれからいろいろな定理を生み出していけたらと思います.
全仏オープン2015を観てきた(エッフェル塔&Roland-Garros)
せっかくパリにいるんだし,ということで.
6/3の準々決勝「錦織 vs. ツォンガ」戦をエッフェル塔の特設スクリーンで,6/7の決勝「ジョコヴィッチ vs. ワウリンカ」戦を現地Roland-Garrosで観戦してきました.
エッフェル塔特設スクリーン
自宅で中継みてるんだけど,まったく論文書きに集中できないのでエッフェル塔行ってくる > 全仏オープン
— Ryoma Sin'ya (@sinya8282) 2015, 6月 2
エッフェル塔の特設スクリーンで錦織 vs. ツォンガ戦を観てた. pic.twitter.com/FzaYI7PL5n
— Ryoma Sin'ya (@sinya8282) 2015, 6月 2
大勢のパリ市民が草むらに座ったり寝転んだりして,まったりとテニスを観戦していました.やはりフランス人であるツォンガの応援が圧倒的多数.(でも日本人もちらほら錦織選手を応援してましたよ!)
特設スクリーンだけでなく特設コートや専用ブース,ブティック(全仏オープングッズの出店)などもあり,なによりエッフェル塔にも巨大なボールが飾られてたり,全仏オープンはパリ市民に愛されてるんだな,と感じました.
結構な人数がビールやワインを楽しんでいました.僕も白ワインを飲みながら観戦.
普通に昼からお酒を飲むお国柄は良い.
Roland-Garros
パリは西側,ブローニュの森の端っこにあるテニス施設(公園).
チケットはインターネットで購入&Eチケット発券,Eチケットを印刷して(顔写真付きの身分証明書と一緒に)当日入場時に係員に確認してもらう仕組み.公園に入場するだけで25€.とうぜん,決勝戦が行われるセンターコートに入るにはもっとお金を使う必要があります(いくらなんでしょうね?).
正にお祭り,という感じ.楽しい!
テニスグッズ販売店が異様にオシャレ... 流石パリ.
よくできたミニテニスラケットを購入.24€だったのが最終日価格で15€に!(ちなみにナダルのモデルのミニチュアらしいです)
炭酸飲料『perrier』もRoland-Garros特別仕様な容器で発売されてました.
決勝戦が行われたCourt Philippe-Chatrier.いわゆるセンターコート.
センターコートの外でも色んな所にスクリーンがあって試合を楽しめる.
いちばん人が集まってたのは,センターコート直ぐ横の巨大スクリーン.巨大なクッションに寝っ転がって観戦してる人たちが羨ましい...
コスチュームがかわいいと話題のボールガールも最前列で固まってみてました.
自宅のTVで快適に観戦するのも良いですが,現地で大勢のファンと共に盛り上がるのも楽しい.
最後の表彰式の時はチケットがない人でもセンターコートに入ることができました!
遠目だけど生でファイナリストを観ることができて感激 :-)
留学期間を半分終えて
4月は研究議論や進学手続き等のため日本に一時帰国していて,5月頭パリに戻ってきました.日本一時帰国の内容も後日記事にしたいと思います.
パリに戻ってくると,自宅近くのジョルジュ・マンデル通りの木々に花が咲き誇っていて,(100%妄想ですが)歓迎してもらってるようでウキウキしてしまいました.
パリではこの木を良く見かける気がします.なんという名前の木なのでしょうか.
さて,去年の10月にフランスに渡ってからおよそ半年+一ヶ月経ちました.
あっという間すぎる
というのが率直な感想です.
- 1〜2ヶ月目はパリでの生きてくためにやるべきことが多くて時間があっという間に過ぎた
- 2〜3ヶ月目は大学生活に馴染むためにやるべきことが多くて時間があっという間に過ぎた
- 3~5ヶ月目はようやくゆっくり研究,,,と思いきや新しいテーマなのでじっくり学習していたらあっという間に過ぎた
- 6ヶ月目〜今になってあと半年しか無いことに気付いて焦る
という感じです.半年パリで過ごしたわりには,研究・仏語・文化交流それぞれの方向であまり進捗がないように感じ,少々もどかしいです.
フランス食材での自炊はとても楽しく,知り合いも増えたので生活はとても充実していますが :-)
特にフランス語は全然上達しませんね...
大学の人たちは皆英語が上手なのでついつい英語で議論してしまいます.フランス語を使わなくても意思疎通が出来るわけです.そのためフランス語勉強はかなりサボっていました(単語帳をパラパラ眺める程度).
とはいえフランス語
僕の分野では特に重要だと思います.フランスの正規言語学派は歴史的にも現在もスター揃いで,この留学が終わってもフランスの研究者達とは交流が続くはずです(続かせたいです).フランス語を喋れたほうが確実にパリでの(大学外での)生活も充実します.
彼らはフランス語に誇りを持っています(少数ですが僕の観測範囲内だと博論は仏語で書いてる人が多いです,そういうものなのでしょうか?).読まねばならない重要な論文がフランス語ということも良くあります.
なによりその国の母国語を話せない限り,その国に本当の意味で受け入れられない気がします.
ということで,知人に薦められた「独習向け」のフランス語によるフランス語テキストを購入しました.独習+実践訓練で頑張っていきたいと思います.実践訓練には困りませんからね ;-)
正規表現技術入門という本を書きました
正規表現の入門書を書きました.
紙の本はネット通販ではAmazonさん,7netショッピングさん,hontoさん,ヨドバシ.comさんでの取り扱いを確認しています.
もちろん電子書籍版もあります.今の所電子書籍版は技術評論社さんの通販サイトだけで買うことができます.
本当に入門書ですか?
はい.正規表現を全く知らない人でも読めることを念頭に,
- そもそも正規表現って何?から始まり
- わりやすい例題や面白い歴史話・小話を交えつつ
- 説明の飛躍が無い用に丁寧に正規表現の仕組みを解説
しています.加えて,各話題それぞれのエキスパートが
- 高度な内容も曖昧な記述やごまかしや嘘をつかわずに説明する
ことを念頭に記述されています.
純粋な入門者の視点で,本書の構成・文章・表現の校正に多大なる時間を割いてくれた技術評論社の方々には本当に感謝しています.
ぜひ本記事に併せて正規表現技術入門特別コラムも御覧ください.
番外編●特別コラム「[知っておきたい]正規表現にまつわる基本Q&A」[正規表現技術入門――最新エンジン実装と理論的背景(WEB+DB PRESS plusシリーズ)]|gihyo.jp … 技術評論社
本書の特徴
プログラマ向けの正規表現の本はたくさんあります.
そのなかでも本書が特に目立つ点としては
- 正規表現の仕組みや
- 面白く奥深い正規表現の歴史や
- 正規表現の仕組みを知った上での上手な使い方を説明している点
にあります.
ぜひ,忌憚のないご感想を
本書に目を通してくださった皆様,ぜひ感じたままの意見を発信して下さい.著者陣へのフィードバックにもなり,あるいは著者陣からの応答やフォローもあるかもしれません.
どうぞ,正規表現技術入門をよろしくお願いします.
12月から1月のパリの風景
クリスマス・シーズンから新年にかけてのパリの風景を適当に纏めてみました(年越しの瞬間の写真はまた別の記事でまとめます).この時期は論文書きで忙しかったので写真は少なめだけれども,イベントシーズンだけあって普段とは違ったパリが楽しめました.
パリ市庁舎前にスケートリンク!
パリ市庁舎前は普段から色々なイベントがあってなかなかに楽しい場所です.12月中盤から2月現在まではなんとスケートリンク(!)が設置されていました.いつも多くのパリ市民で賑わっています.知人曰く「フランス人はスケート好き」らしい(笑)
どこにでもクリスマス・ツリー
これは空港.
これは我が家(マンションの入り口に)
ノートルダム大聖堂前にも.綺麗.
ノートルダム大聖堂前のクリスマス・ツリーは,1月末まで飾られていました.急いで片付けるなんてことはしないようですね.
クリスマスということで(?)レゴの展示
Passyのデパートにて.ハリー・ポッタをモチーフにしたレゴ作品が子どもたちを喜ばせていました.よく出来ている!
あとは適当に風景を
凱旋門とエッフェル塔.かなり綺麗に取れたお気に入りの写真.
冬.自宅の窓から.
Bir-Hekim橋から眺めるエッフェル塔.毎日この風景を見ながらメトロで通学しています.何気にトロカデロ広場から眺めるエッフェル塔より好きかもしれない.
写真じゃわかりにくいかもしれないけど,2/5にパリで初めて少しだけ雪が降った.パリは雪はなかなか振らないそうです.ちなみに写真は大学のオフィスの窓から(1時間ぐらいでやんじゃった).
フランス学生ビザの取得 (学振持ちがグランゼコールの客員博士学生として1年間の留学)
先日パリの移民局(OFII)にてようやく学生ビザを有効化してもらったので,ビザ取得までのプロセスを簡単にまとめたいと思います.
留学手続きの流れは,それぞれの留学事情にそって人それぞれだと思います.
僕の場合は
- 学振持ち(DC2)
- パリのグランゼコール:Télécom ParisTech に客員博士として2014/10から1年間の受け入れが正式に決まっていた
- というかParisTechの学生書をビザ申請時点で既に取得していた
- パリでの住所・銀行口座・電話番号をビザ申請時点で既に持っていた
という状況だったので,ビザ手続きは終始スムーズに進みました.
手続きの流れ
Web上にはフランス留学のための学生ビザ取得に関するブログや記事がいくつかありますが,また比較的僕に似た状況での留学情報を記した「博士課程院生のフランス留学」さんの記事が参考になりました.
フランスに学生として3ヶ月以上滞在するためには,学生ビザの取得が必要です.さらに,学生ビザ取得のためには,日本にいる間に「Campus Franceへの登録及び面接」「フランス大使館へのビザ申請」を済ませ,フランスに渡った後も「フランスの移民局にて学生ビザの有効化」というステップが必要となります.
学生ビザ取得に関する一般的な情報はCampus Franceや在日フランス大使館,あるいは上のブログ記事にある程度纏められています特にCampus Franceが用意してくれている学生ビザ取得までの手続きの流れをまとめたPDFがナイスです.
とはいえ,僕が学生ビザの取得に至るまでの経緯は,上の図の流れからは大きくそれていました.
- 6月にParisTechのJacques Sakarovitch先生へ留学の件をメールで打診
- いくつかのやりとりを経て7月終盤,10月からの留学受け入れOKメールを貰う(この辺の話はこのブログの最初の記事にも書かれています)
- 8〜9月,留学手続きに関して,Sakarovitch先生にCVを送る意外特に何もしない(Campus Franceへの登録すらしませんでした)
- 10月,ビザも取得せず家も決まっていない状況でにフランスに行く
- フランスに渡ってからようやく学生ビザ申請の手続きを進める(Campus Franceの登録もパリで行った).
- 11月,在日フランス大使館にビザを申請するために日本に一時帰国
- 12月,在日フランス大使館での手続きを終えてパリに戻る.
- 今年1月末,パリの移民局(OFII)にて学生ビザの有効化を済ませる <- new!
という状況です.「8〜9月何してたんだ??」と言われるかもしれませんが,この時期は学会出張や論文執筆で忙しかったので,Sakarovitch先生からOKメールを受け取った時点で「ビザ手続きについてはとりあずパリに行った後考えよう」という意識でした.
学振持ち
日本学術振興会が行っている「日本のトップクラスの若手研究者に対する支援制度」として特別研究員というものがあります.(少なくとも僕の周りでは)この特別研究員に採用されている学生さんのことを「学振持ち」と言ったりします.特別研究員制度にはPD・DC1・DC2等の種類がありますが,僕の場合はDC2に採用されています.
具体的には,この制度に採用されるとゲンナマが貰えるということです.嬉しいですね!(DC2の僕の場合は月々の20万円のお給料と年間100万円を上限とした研究費を頂いています)
「学振持ち」という状況は,フランス留学のための学生ビザ取得のハードルをとても大きく下げます.学生ビザの取得のために必要とされている
- Campus Franceでの面接及び手続料金の免除
- 留学生活に必要な経済証明(在日フランス大使館は最低限の生活費用として毎月最低615€の経済証明をビザ申請時に要請します)
という2つの大きな問題を解決してくれるからです.*月20万円のお給料はだいたい1400~1500€なので,物価の高〜いパリでも普通に暮らして行けます.
持ってて良かった学振
「CEFの取り決めにより, 次のいずれかの奨学金受給者は、Campus France-CEF の面接および手続き料金の支払い全額が免除されます → 学振」 http://t.co/bBJOhQVN57 面接免除きたーーーーー!!!持っててよかった学振.
— Ryoma Sin'ya @巴里留学中 (@sinya8282) 2014, 10月 5
学生証・住まい・口座や電話などのパリでの生活に必要なモノがビザ申請時点で既に揃っていた
普通は上記「手続きの流れ」の図の用に,留学が決まった時点で日本にいる間にフランス大使館に申請を行います.しかし,僕の場合は先にパリに行って生活に必要なモノ一式を揃えた上で申請していたので,各種書類の提出が非常にスムーズになりました.これだけモノが揃った状況で申請が却下されたり滞ったりするわけないだろ!(という気持ちでスムーズに申請が通るよう祈っていました).
ちなみに西麻布にある在日フランス大使館はなかなかシャレオツな外見でした.
パリの移民局にて学生ビザの有効化
日本でやるべきことを終え,パリに戻ってもまだ学生ビザの手続きは終わっていません.在日フランス大使館で貰った書類をフランスでの住所を管轄している移民局に送り,移民局からの招待を待ち,必要書類の提出や健康診断を行って学生ビザの有効化を行います.
この手続きに関しては在日フランス大使館のページやビザ申請時に受け取る書類に詳しく書いてあります.また,多くのブログ記事で手続きの様子がまとめられています.
僕の場合はパリ在住なので,パリはバスティーユ近くにある移民局にて手続きを行ってきました.フランス語が全く話せない僕ですが,手続きはスムーズに進み,健康診断も含め1時間30分程度で終わりました.移民局スタッフの手際は非常に良かったです.健康診断のための医療スタッフや受付案内係り含め,総勢20人ぐらいいたと思います.受付案内係のほとんどは英語が話せない雰囲気でした(でも書類見せればOK).
感想
結局,10月にビザ無しでフランス入りしてから4ヶ月後の翌年1月末に学生ビザを取得することになりました.日本に一時帰国していた1ヶ月間を除くと,フランス滞在およそ八十数日目でのビザ取得です.90日間のビザなし滞在可能期間ギリギリでした.
結果的には「ビザ手続きについてはとりあずパリに行った後考えよう」という8月時点での僕の考え悪い選択ではなかったように思えます.行き当たりばったりでもなんとかなるものです.行動したもの勝ちです.