<pre>この例 (a|b)^n c (a|b)^* a (a|b)^n は</pre>

<pre>Context Free Language の有限個の intersection では作れないけれど</pre>

<pre>Conjunctive Grammar http://users.utu.fi/aleokh/conjunctive/ という、 ルールの中でもintersectionを取れる文法なら書ける</pre>

<pre>という境界例で出てきてたもの。</pre>

<pre>正確には、{wcw | w∈{a,b}*} がConjunctive Grammarだと書けるそうな</pre>

<pre>intersectionに加えて (a|b)^n c (a|b)^* a (a|b)^n が書けないと書けなさそうなので PEGだとこっちが難しい</pre>

<pre>あと、deterministic context-free grammar で回文が書けない証明を読んでました。 結構しんどかった。</pre>

<pre>原論文っぽいの読んだので、最近はもっと簡単になってるのかもしれないけど。</pre>

<pre>原論文っぽいのは、上の方で書いた「正規言語はpostfix indexが有限」の拡張みたいなことをやっていた</pre>

<pre>「DCFGで書けるならば、ある文字列to文字列の関数Eが存在して、index(w++E(w)) は有限通り」</pre>

<pre>らしい</pre>

<pre>E(w)は、直感的には、deterministic pushdown automaton のwを読んだ後のスタックをできるだけ限界まで消費するような文字列を計算する関数で、そうやってスタックの底をつかせると状態パターン数がほとんどないはずなので有限に落ちるらしい。</pre>

<pre>Stephen N. Cole &quot;Deterministic Pushdown Store Machines and Real-Time Computation&quot; Journal of the ACM, 1971.</pre>

<pre>.</pre>

<pre>ところで、僕の言ってることが意味不明だったら容赦なく突っ込むといいと思います＞ALL。さっきから専門用語を連発しすぎている気が自分ですごくしている</pre>

<pre>PEGどころかdeterministic PDAで書けないという証明もなかなかできないでいる</pre>

<pre>さっきの回文の時の方法を使おうとしても E(w)=a^(|w|+1) を取るとすぐに有限にできてしまう</pre>

<pre>です</pre>

<pre>hogege</pre>

<pre>これだと後ろに a^2|w|+1 文字を足すまでは無条件acceptで、それ以降は1番目に足した文字、2番目に足した文字、…に依存、だから、|w|に応じて全部違うindexになる</pre>

<pre>おお</pre>

<pre>おおじゃなくて、任意のE</pre>

<pre>に対して有限になることを言わなければ</pre>

<pre>論文では、「DCFGなら有限になる、逆は、わからないけど、ならないんじゃないかな。Eが計算可能、くらいの制約つければなるかも」と書いてありました</pre>

<pre>その語の展開は調べてないです</pre>

<pre>どんなEをとっても、任意のn∈Nに対して|w1++E(w1)|,...,|wn++E(wn)| が全て異なるような w1 から wn をとれる。そしてこいつらのindexは全部異なる。ので、常に無限。</pre>

<pre>よしこれだ。</pre>

<pre>w_{i+1} = a^{|w_i++E(w_i)|+1}</pre>

<pre>しかし (a|b)^n c (a|b)* a (a|b)^n はやっぱり難しいな。E(w)はw++E(w)がちょうどマッチするように伸ばす関数にしちゃえば有限だ。</pre>

<pre>適当にぐぐった http://web.cs.wpi.edu/~kal/PLT/PLT4.1.2.html</pre>

<pre>wikipedia http://ja.wikipedia.org/wiki/%E5%B7%A6%E5%86%8D%E5%B8%B0</pre>

<pre>文字列長の線形オーダでparseができるようになったら、それはやっぱりえらいことな気がする</pre>

<pre>CFG⊆PEG の&quot;構成的な&quot;証明ができれば、ですけど、まあ一応</pre>

<pre>あと、parseというかCFGに入るかの検査は線形オーダでも、構文木を復元するのはえらい計算量になるような変換しか見つからない可能性もある</pre>

<pre>CFGのparsingの計算量と言えば、暇があったら http://arxiv.org/abs/math.GR/0307321 と http://arxiv.org/abs/math.GR/0511460 読みたい。</pre>

<pre>多倍長整数の乗算をFFTで周波数の世界にもっておくと速くなるようなノリで、行列を怪しげな群にもっていくと行列乗算が速くなりそうらしいという話</pre>

<pre>オートマトンとか形式言語の方で 怪しげな群とかモノイドとかに持って行く話で面白そうな結果を最近よく見かけるので なんかまとめて勉強したいなあ</pre>

<pre>a^n b^n c^n の方が読めない^^;</pre>

<pre>＞a^n b^n c^n</pre>

<pre>合ってるのかなこれ</pre>

<pre>gが空文字列にマッチしないという仮定の下で (!e)fg ==&gt; (e _* / f)g</pre>

<pre>ka</pre>

<pre>かな</pre>

<pre>なんか違う</pre>

<pre>いやあってる</pre>

<pre>つもり</pre>

<pre>======================================= 終 了 ===============================</pre>

<pre>パチパチパチ</pre>

<pre>いやーしかし全然ダメだった。僕の今日の成果はDPDAのfinite-indexの作り方を学んだというだけに終わってしまった。</pre>

<pre>あとでblogにまとめとくかなあ</pre>

<pre>で、あと空文字列にマッチするパターンはものすごく注意深く使う</pre>

<pre>で、実用してて変な問題にあたる気もあんまりしないけどなあ＞PEG</pre>

<pre>証明するときには context-free という性質はものすごい扱いやすいことを実感した。</pre>

<pre>・定期経過報告タイムでも設けた方が面白かったかもしれない</pre>

<pre>・チュートリアル的な云々はちゃんと資料準備した方がよかった。アドリブでなんとかなると思ってたのは甘かった</pre>

<pre>・やっぱチャットだとインタラクションは難しいな。といってオフで集まっても今以上にgdgdになりそうではある</pre>

<pre>どのくらいこのletmein</pre>

<pre>リンクはバラまいていいものなんだろう</pre>

<pre>僕はletmein=scalaから入ったのにscala部屋に行ったことが一度もないダメ人間</pre>

<pre>わざわざイベントにしないと「一日集中して」なんて結局やらないで終わる傾向にあるので、無理矢理機会を作る作戦です。</pre>

<pre>もちろんCPonリベンジもありです。</pre>