計算機科学のブログ

帰納的定義と証明技法 文字列に関する構造帰納法 文字列の帰納的定義 文字列の連結、反転、逆順

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

初期段階。

λ - 1 = λ

は

Σ *

の要素を反転した要素である。

帰納段階。

w が

Σ *

の要素を反転した要素で x が

Σ

の要素ならば、

w - 1 · x

は

Σ *

の要素、 つまり

x · w

は

Σ *

の要素を反転した要素である。