計算機科学のブログ

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

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

任意の文字列vに対して

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

任意の文字列w とある

Σ

上の文字xに対して、

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

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

Σ

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

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

が成り立つ。