計算機科学のブログ

帰納的定義と証明技法 回文(palindrome)、文字の集合、文字列、連結

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

初期段階。

空列は回文にあてはまる文字列Dの要素である。

λ ∈ D

帰納段階。

wが文字の集合

Σ

の要素、 xがDの要素のとき、

w x w

はDの要素である。