言語の定義例

BECCAのI'm　Alive を聴きながら手元の資料に目を通す(youtubeが別窓で開くよ！)


記号列xにおいて、x^R = xを満たすものと回文と呼ぶ。
L = ｛ x | x ∈Σ* , x^R = x｝

回文の再起的定義を書きなさい

【解】
(1)，εは回文である。
(2)，x ∈Σ*が回文なら、任意のa ∈Σに対して、axaは回文である。
(3)，上の(1),(2)で定義される記号列のみが回文である。

この解は正しいか？



正しくない。多分・・・

Σ = { a , b , c , … , z }　とする。
εは回文なので(2)を利用すると、aa、bb、ccなどの回文ができる。
さらに続けると、abba、cdeffedcなどの回文が数多く出来る。
しかし、この定義では奇数長の回文（abaなど)は出来ない。
よって正しくない。

多分。


(1)の条件を、「εと長さ1の記号列は回文である」にすればいいのかな？

明日の授業でわかると思う。



それにしても、カントールの対角線論法がいまだによくわからない