Palindrome 11【Markov Algorithm Online】

https://mao.snuke.org/tasks/15
解法のネタバレがあります！

yyes1:yyes0yyes0
yyes01:1yyes0
yyes00:0yyes0
yyes0yno:yno
0yyes0yyes0:yno
1yyes0yyes0:
1yyes0:yno
0yyes0:
yyes0:
yyesy::
:yyes

よく分からないコードになりました。
13 手解から変形させると分かりやすいです。

13 手解
t0:#
t1:##
#1:1#
#0:0#
#f:f
0##:f
1##:
1#:f
0#:
#:
tf::no
t::yes
:t

13 手解です。まず先頭に t を作って、先頭の文字が 0 なら #、1 なら ## に符号化して末尾に送ります（符号化は一進数でやるとコスパがいいです）。
末尾に着いたら先頭と末尾が合っていれば両者を消して、合わなければ f に化けます。
最終的に f があれば no で、なければ yes という感じのコードです。

t、f の代わりにいい感じに yes、no っぽい文字列を使うことで、停止規則を 1 つにできます（自由な文字列を含む規則は、文字列をいい感じにごにょるとまとめられることがあります）。

12 手解
yyes0:#
yyes1:##
#1:1#
#0:0#
#yno:yno
0##:yno
1##:
1#:yno
0#:
#:
yyesy::
:yyes

# にまだ自由度があって、12 手解の一番上の規則を見ると # を yyes0 にすればこの規則が除けることが分かります（自由な文字列を含む規則は、文字列をいい感じにごにょると削除できることがあります）。
実際に # を yyes0 で置き換えると冒頭の 11 手解になります。

まとめ

最短手数の公式: なんかいい感じのやつ - (自由な文字列の種類数)