再帰データ型について

どういう意味ですか（ ; ; ）

アルファベットの集合Aの再帰データ型A*は以下のように定義される。

基礎ケース
A*は空の文字λを含む

構成ケース
a ∈ A,s ∈ A* ならばペア<a,s>∈ A*

ozwk

2019/12/02 01:25

そのまんまの意味ですとしか答えにくいので何がわからないのか/納得いかないのかを書くといいかと。

_._._ami

2019/12/02 23:55

すみません、初めて利用したので認識不足でした。次回から気をつけます。ご指摘ありがとうございました！

行動規範の内容に同意します

回答1件

ベストアンサー

再帰的(recursive)な定義というのは、起点となるものの定義（質問の場合は、基礎ケース「Aは空の文字λを含む」)と、それを拡張させていく方法の定義（質問の場合は、構成ケース「a ∈ A,s ∈ A ならばペア<a,s>∈ A*」）で構成されます。

仮に、アルファベットの集合Aが、３つのアルファベット'A','B','C'を含むとします。
それを['A','B','C']というように表すことにします。

そうすると、
・λだけを含む集合Aは、集合Aの再帰データ型です（基礎ケース）:　Aは[λ]と表せます。

・それに、’A'を加えた集合　[λ,'A']には、ペア　<λ,'A'>が含まれます(構成ケース)。
・さらに、’B'を加えた集合　[λ,'A','B']には、ペア　<λ,'A'>と<λ,'B'>と<'A','B'>と<λ,'A','B'>とが含まれます。
というように再帰データ型A*は拡張・再構成され得て、
[λ]
[λ,'A']
[λ,'B']
[λ,'C']
[λ,'A','B']
[λ,'A','C']
[λ,'B','C']
[λ,'A','B','C']
のいずれかになり得ます。