-
- いいね！0
Sosuke MORIGUCHI
@chiguri
具体的には以下の折り返し（2から6） abaabba abaabbaaabbba abaabbaaabbbaaaabbbba abaabbaaabbbaaaabbbbaaaaabbbbba abaabbaaabbbaaaabbbbaaaaabbbbbaaaaaabbbbbba
2015-11-14 03:27:59
Sosuke MORIGUCHI
@chiguri
@kmizu フフフ・・・とりあえず折り返しまでに「折り返しの基点になりそうもない」ように文字列をつなぐとなんか通るので・・・（なんかすごく感覚的ですが）
2015-11-14 03:35:40
Kota Mizushima (on a diet)
@kmizu
@chiguri 確かに。なんかちょっとでいけそうと思うと（実際はそんなに簡単じゃなくても）、もう少し考えれば…と思っちゃいますね…
2015-11-14 04:03:33
Sosuke MORIGUCHI
@chiguri
で、それは「基点を含んで成功してしまう部分がある」ことが問題で、しかもちょっとこまるのは「その部分の開始を他の理由で吹っ飛ばす」と通ったりするんだよなあｗ
2015-11-14 04:20:36
Sosuke MORIGUCHI
@chiguri
さっき自分で作った例は、成功→失敗のときに必ず基点までの距離以下でしか成功できないようになってるからだろうなあ。
2015-11-14 04:25:37
Sosuke MORIGUCHI
@chiguri
認識されるための十分条件： 折り返しまでの文字列をs、長さをlとする。 0<n<m<=lであるn,mについて、sの"後ろn文字"と"後ろm文字を反転させたもの"をつないで回文を作れなければ必ず認識される。
2015-11-14 04:35:44
Sosuke MORIGUCHI
@chiguri
（言い換え）認識されないための必要条件： 折り返しまでの文字列をs、長さをlとする。 認識されない場合、0<n<m<=lをみたし、かつsの"後ろn文字"と"後ろm文字を反転させたもの"が回文となるようなnとmが存在する。
2015-11-14 04:41:19
Sosuke MORIGUCHI
@chiguri
aAa / ()だと、うしろから2,4(2*2).8(4*2),16(*2)と成功して直後に失敗するせいでそこまで一気に巻き戻るからその総和で成功する区切りが2^n-2になる。
2015-11-14 05:00:44
Sosuke MORIGUCHI
@chiguri
ああ、うん、recursive descentなプログラム書いて良かった。かなり脳内で動きを追えるようになってきた。
2015-11-14 05:01:15
Sosuke MORIGUCHI
@chiguri
あとは・・・ちょっと違う方法だけど、この回文っぽいPEGで認識する文字列sについて、s aa sは認識されるっぽい。逆にs sは認識されないっぽい。（ちょうど飛ばすため）
2015-11-14 05:16:13
Sosuke MORIGUCHI
@chiguri
なお、同じ文字だけで作ると、さっきの式からは (2^n-2)*2+2=2^(n+1)-2となるからまあなんとなく分かるかと。
2015-11-14 05:17:41