編集可能

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

タイトルの通りです。主に @kmizu@chiguri さんが考察しています。
システム管理 運用 プログラミング peg
1
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
しかし、ここまで例を増やしてみてもわかる気がしないなあ
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になりそう?
Kota Mizushima (on a diet) @kmizu
記号1種類のときに出てきた、2の冪乗 - 2回の繰り返しという要素が、記号の種類増やすとどっか行ってしまった感じが釈然としなかったが、これなら納得でき、そうだ。
残りを読む(27)

コメント

コメントがまだありません。感想を最初に伝えてみませんか?

ログインして広告を非表示にする
ログインして広告を非表示にする