A <- "a" A "a" / "b" A "b" / ""が受理する言語はいかなるものか？

Kota Mizushima (on a diet) @kmizu

qnighy.hatenablog.com/entry/2015/11/… の回文のようでいてそうでないPEGが一体何を表しているのか気になってちょっとだけ考えてみたら、凄く珍妙な言語になってることに気づいた…。 gist.github.com/kmizu/d057ba7d… #peg

Sosuke MORIGUCHI @chiguri

@kmizu babbabとかはTrueでbaaaabとかはFalseなので、「2回連続するなら折り返しにも2回、そうでないなら1回」みたいな感じですかね・・・

Kota Mizushima (on a diet) @kmizu

@chiguri babbabとかはサンプルに入れてなかったですね。例をもうちょっと網羅的にして考えなおす必要がありそうです。ありがとうございます。

Kota Mizushima (on a diet) @kmizu

入力を網羅的にしたら、こんな gist.github.com/kmizu/d057ba7d… 感じになった。ふむー。 #peg

Kota Mizushima (on a diet) @kmizu

長さ8文字までやってみたが、うーん…。わかったようなわからないような。 gist.github.com/kmizu/d057ba7d… #peg

Kota Mizushima (on a diet) @kmizu

文字数が増えてくると、手作業でやるとしんどくなってきたので回文ジェネレータ作った。 gist.github.com/kmizu/d057ba7d… #peg

Kota Mizushima (on a diet) @kmizu

さらにプログラム修正してみた gist.github.com/kmizu/d057ba7d…

Kota Mizushima (on a diet) @kmizu

しかし、ここまで例を増やしてみてもわかる気がしないなあ

Sosuke MORIGUCHI @chiguri

@kmizu 折り返し時点でなんらかの「きりの良さ」がないといけない気がするんですが、イマイチどういうものかぴんとこないんですよねえ・・・

Kota Mizushima (on a diet) @kmizu

@chiguri そうですねえ。類似の文法 A <- "a" A "a" / "" のときの経験から察するに、長さが2の冪乗-nのときががなんか関係してる気がするのですが…

Kota Mizushima (on a diet) @kmizu

形式としては、 {a^{2**n - 2}}∪{b^{2**n - 2}}∪{aとb両方が出現する何らかの言語} な感じになるはずなんだな、たぶん。

Kota Mizushima (on a diet) @kmizu

@kmizu ちなみに、a^nでaがn回出現する、を、2**nは2の冪乗を表すとする。

Kota Mizushima (on a diet) @kmizu

gist.github.com/kmizu/d057ba7d… 眺めててピンと来たのでメモっておこう。回文に含まれているaまたはbの部分列が2**n - 2回のみ出現する場合にはマッチしている。たぶんこれで確定だと思うけど、簡潔に条件書くにはどうすればいいんだ…。

Kota Mizushima (on a diet) @kmizu

と思ったけど、 checkPEG grammar "abaabaabaaba" = False のケースがあるから、条件足りないかorz 列としての連続性を考えずに、単純にaの出現回数、bの出現回数で考えればOKかな？（要考察）

Kota Mizushima (on a diet) @kmizu

ちゃうちゃう（自己ツッコミ）。ここで、記号の「連続」を、記号の隣接でとらえたらダメで、「外から囲んで」連続しているかが問題だ。 "abaabaabaaba" なんかは、aa ..... aa で4個のaが連続しているようにとらえるべき。お。なんか見えてきた気がするぞ。

Kota Mizushima (on a diet) @kmizu

「外側から囲む」連続性（何というのが正しいのかちょっとわからない）で考えると、 checkPEG grammar "baaaaaaaab" = False checkPEG grammar "abaaaaaaba" = True になる理由も説明つく。

Sosuke MORIGUCHI @chiguri

・・・あれ、昨日動いたghcがなんか拗ねてる・・・

Sosuke MORIGUCHI @chiguri

と思ったら二回目で動いた。

Kota Mizushima (on a diet) @kmizu

前者はaが8カウント(2**n - 2回の繰り返しでない)、後者は内側のaが6カウント(2** n -2回の繰り返し)、その外側のaが2カウント、その外側のbが2カウントとなっており、うまく当てはまっている。

Kota Mizushima (on a diet) @kmizu

あとは、この仮説をプログラムに落として、自動生成した回文に食わせればだいたいあってそうかの判定はできるかな。

Sosuke MORIGUCHI @chiguri

←なんか向きになって反例を探す人

Sosuke MORIGUCHI @chiguri

@kmizu checkPEG grammar "abaabbaaabbbaaaabbbbaabbbbaaaabbbaaabbaaba" = True こんなんどうでしょう。真ん中付近の4つずつあたりがくせ者かと。

Sosuke MORIGUCHI @chiguri

うん、a^{i}b^{i}を1からnまで並べて、そのあとにa一つだけであとは折り返すやつを作ってみたらTrueになりそう？

Sosuke MORIGUCHI @chiguri

6までは確認できた。

Kota Mizushima (on a diet) @kmizu

記号１種類のときに出てきた、2の冪乗 - 2回の繰り返しという要素が、記号の種類増やすとどっか行ってしまった感じが釈然としなかったが、これなら納得でき、そうだ。