計算機科学のブログ

帰納的定義と証明技法 文字列に関する構造帰納法 文字列に対する処理 連結した文字列の長さと文字列の長さの和

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第3章(帰納的定義と証明技法)、3.3(文字列に関する構造帰納法)、3.3.2(文字列に対する処理)の問3.9の解答を求めてみる。

任意の文字列vに対して

l(vλ)=l(v)=l(v)+0=l(v)+l(λ)

任意の文字列w とある

Σ

上の文字xに対して、

l(v(wx))=l((vw)x)=l(vw)+1=l(v)+l(w)+1=l(v)+l(wx)

よって、帰納法により、 任意の

Σ

上の文字列 v、 w に対して、

l(vw)=l(v)+l(w)

が成り立つ。