やったこと

バイトをしていた

先読み/後読みを持った正規表現をDFAに変換できた。まさか本当にできると思わなかったがなぜか出来てしまったのでできるのだと思う。

以下、資料など。

• 先読み付き正規表現の有限状態オートマトンへの変換
  https://www.jstage.jst.go.jp/article/jssst/29/1/29_1_1_147/_article/-char/ja/
  めっちゃ参考にしたやつ。先読みはBFAで綺麗に実装できるのだけど後読みは‥‥。

• アトミックグループで拡張された正規表現のオートマトンへの変換
  http://ci.nii.ac.jp/naid/110009517217
  アトミックグループにちゃんとした意味論を与えたことに意義があるのだと思う。

• 詳説 正規表現 第3版
  https://www.amazon.co.jp/正規表現-第3版-Jeffrey-F-Friedl/dp/4873113598
  読みたい。

• Regular Expression Matching Can Be Simple And Fast
  https://swtch.com/~rsc/regexp/regexp1.html

  The generalized assertions are harder to accommodate but in principle could be encoded in the NFA.

  とか書いてあるけどソースを教えてくれ〜。

思うこと

PEGの言語のクラス=TWDPDA without Endmarksの言語のクラス？

なのではないかと考えていた。TWDPDAというのはTwo-Way Deterministic Push-Down Automataのことで、これは性質がPEGによく似ている。例えばA^nB^nC^n言語（AとBとCがそれぞれ同じ数含む言語）を受理できたり、文脈自由文法の言語のクラスと比較不能だと言われていたり（未解決）、メモ化することでO(n)で受理するかどうか判定するアルゴリズムが知られていたりする。ただ、TWDPDAは回文を受理できる気がする（文字を全てスタックしながら最後まで読んで、最初まで戻ってから今度はスタックした文字と一致するか確認しながらポップしていて最後まで読めたら受理する、みたいな）ので、TWDPDAからEndmark（末尾を表す特別な記号）を除いたものがPEGなのでは？　という発想。

これを証明するためには多分、PEG→TWDPDAの変換とTWDPDA→PEGの変換を示せれば良いと思う。PEG→TWDPDAは何となくできそうな気がするのだけど、TWDPDA→PEGはそれなりに難しそうな気がする（FA→正規表現が難しいように）。どっちにせよ変換後の言語が同じものになっていることを示すのが難しそう。PEG parsing machineというPEGに対応する仮想機械があるらしいので、それからTWDPDAに変換したりすれば単純になるかもしれないけど、厳密にPEG=PEG parsing machineなのか調べられていないので何とも言えない。

これが証明できると何が嬉しいのかというと、多分そんなに嬉しいことは無い。というのもTWDPDA自体がPEG同様謎に満ちた存在で、結局CFGとの関係も良く分かっていないから。ただ、PEGという比較的新しい概念がTWDPDAという半世紀以上前からある概念と結び付けば、これまで見えてこなかったものが見えてくる可能性は十分にあると思う。あってほしい。

資料。

• Two-way pushdown automata
  http://www.sciencedirect.com/science/article/pii/S0019995867903695
  TWPDAについての論文。45Pあってしんどい。最初のTWPDAについての定義しか読めていない。むずい‥‥。

• Parsing Expression Grammars: A Recognition-Based Syntactic Foundation
  http://bford.info/pub/lang/peg
  言わずと知れたPEGの論文。一度通して読んだのだけど内容が記憶から吹っ飛んでいるので読み直している。面白い。

• 形式言語とオートマトン
  https://www.amazon.co.jp/形式言語とオートマトン-Information-Science-Engineering-守屋/dp/4781909906
  AFAやTWPDAについて触れられていてすごく良い本だと思う。少なくとも2000年ころまでのこの分野の研究成果についてすごくまとまっている気がする。

• 計算理論の基礎 [原著第2版] 1.オートマトンと言語
  https://www.amazon.co.jp/計算理論の基礎-原著第2版-1-オートマトンと言語-Michael-Sipser/dp/4320122070
  Amazonでの評価が異常に高い。読みたい。

• オートマトンと言語理論
  http://www.ci.seikei.ac.jp/yamamoto/lecture/automaton/text.pdf
  ググったら出てきた良さげな教科書。そのうち確認がてら読む。

気になるのは、どうしてこんな本を眺めてれば気付くような関係について論じている人がいないのか。サーベイ不足感が否めないのでもう少し調査していきたい。