これは何？
MarkovAOで使える括弧列を使ったテクニックについて、知っていることをまとめてみます。
2020/06/01 追記
・規則の誤爆で括弧列が化けることを利用したテク
2020/06/16 追記
・小ネタ
Maxを取る
以下の規則で括弧列の深さのMaxを取ることができます。
)(:
例えばOK/NGを判定する問題等で、OKを()、NGを(())に対応させることで、NGを含むなら結果はNG、そうでないならOKとする処理が実現できます。
例
・()()(())()(())()()(())
)(:を適用していくと、(())だけが残る。
・()()()()()()()()
)(:を適用していくと、()だけが残る。
1規則で複数の文字を消す
a, b, c といった文字を規則中で使っている場面で、
これを ()(), (())(()), ((()))((())) と置き換えてみます。
処理終了後にa:、b:、c:で不要になった文字を消すことをする場合、
():の1規則のみで上記3つとも消す事ができ、規則の節約になります。
これについては、そもそも複数の文字を使わないように最適化した方が有効な場面が多いと思われるため、使いどころは多くないかもしれません。
文字のグループ化
グループ化が適切な日本語か分かりません……
以下の状況を考えてみます。
$ooooa$ooob$ooooc$ooob
aまたはbの左にあるoを消去したいが、cの左にあるoは残したい。
そのままやると以下のようになると思います。
oa:a
ob:b
そこで、aを(())、bを(()())、cを((()()))に置き換えて考えてみます。
$oooo(())$ooo(()())$oooo((()()))$ooo(()())
o(():(()
この1規則で同じ事が実現できます。
(()から始まる括弧列はa,bのみでcにはマッチしないため。
yes/no判定問題に対する応用
(をyeに、)をsに置き換える事で終了規則を節約できる場合があります。
例えば以下のような規則が使われている場面で、
～～～～
)(:
(())::no
()::yes
(をye、)をsに置き換えてみると、()::yesの規則が不要になります（このままの形で使えない場合もある）。
～～～～
sye:
yeyess::no
規則の誤爆で括弧列が化けることを利用したテク
以下の状態から ^ を > に、$ を < に変換することを考えてみます。
before ^oooxxx$
after >oooxxx<
真っ当にやると以下の規則で変換することになると思います。
～～～
^:>
\$:<
～～～
ここで、^を()に、$を(())に、<を(>)に置き換えて考えてみます。
before ()oooxxx(())
after >oooxxx(>)
～～～
():>
～～～
少ない規則で同じ状況が再現できます。
小ネタ
yes/no判定問題に括弧列を使いたいけど、どう頑張っても最終的に((()))とか(())とかになってしまい、yes/no判定問題に対する応用のような事ができない状況への対処方法です。
※)(:の規則を使っている前提です。
括弧列全体を()))～～～((()で囲むと、この例の場合は深さ3までの括弧列が打ち消されて、最後に()だけが残る状態になり、yes/noに当てはめることができるようになります。
yesと判定したい場合は括弧列内で(((())))を生成するか、上の((()の後ろに(())を追加します。
すると、括弧列の深さのMaxに関わらず、noの場合は最終的に()、yesの場合は(())が実現できます。
結果
規則が縮む！！！