多重再帰構文！

今日：1 合計：1286

多重再帰構文とは、

a(X):αXa(a())
a()

上のコードのa(a())のように、再帰関数を２重(あるいはそれ以上)にして呼び出す構文のことです。
一見意味がなさそうに見えますが、この構文にはある効果があります。
とりあえず、下のコードを実際に展開してみましょう。(ギリシャ文字は、例えばsrslなどを表していると考えてください)

a(X):αXa(a(β))
a()

a()を1つずつ展開していきます。

a()
= αa(a(β))
= ααa(β)a(a(β))
= αααβa(a(β))a(a(β))
.....
= αααβααβ...ααβa(a(β)) [ここより右は永久に実行されない]

要するに

α+[ααβ]×無限

となっています。
さて、ここで単に

a(X):αXa(β)
a()

とした場合と比べてみましょう。上のコードを展開します。

 a()
= αa(β)
= ααβa(β)
.....
= ααβαβ...αβa(β) [ここより右は永久に実行されない]

要するに

α+[αβ]×無限

です。二つを並べて比べてみると、

α+[ααβ]×無限 
α+[αβ]×無限

違いは「繰り返し部分の先頭にαがくっついているかどうか」だと分かります。
つまり、この構文には「αをa()で置換できる」という効果があるのです。

ピンと来ないかも知れないので、短縮例を見てみましょう。

a(X):ssXrsssslssa(r)
a()

ssが４回出てきているので、従来の手法なら、

b:ss
a(X):bXrbblba(r)
a()

などとして1B縮めるところです。
しかし、多重再帰構文を使って短縮すると、

a(X):ssXra(a(la(a(r)))
a()

となり、3Bも縮みます！
関数内の'ss'を'a('に置き換える要領です。

関数の中にXが複数入っている場合も同じように短縮できます。
例えば、

a(X):ssXrssXsslssa(r)
a()

なら、

a(X):ssXra(Xa(la(a(r)))
a()

という感じです。
このような場合でも、置換される対象は「最初に出てくるXよりも左にある物」です。

応用としては、引数のある再帰なので、

a(X):αXa(a(βX))
a()

のように成長させたり、

a(X):αXa(a(β))
a(γ)

のように特殊な初項を使ったりすることも出来ます。

問題例