[至急]証明問題がわかりません。

質問

[至急]証明問題がわかりません。

(1)Σ={0,1}のとき、 Σの語wを引数とし、２進数と解釈したときの値を返す関数 φ:Σ*→N を帰納的に定義せよ。（ 0以外で先頭の0は無視し、 εに対する値は0 とする。）

(2)（0以外に0から始まる語はない）正しい２進数およびその値を定義するように上を修正せよ。 εも除外のこと。

証明が苦手で、どのようにしたらよいか見当もつきません。丁寧に詳しく教えてください。よろしくお願いします。

回答No.1

R_Earl · ベストアンサー

> 証明が苦手で、どのようにしたらよいか見当もつきません。

証明問題ではありません。
例えば(1)は「指示された関数を帰納的定義を用いて自由に作ってください」
という問題だと思います。
もしかして問題に取り組む以前に、
出題者が一体何を尋ねているのかが分からないのでしょうか？

> (1)Σ={0,1}のとき、 Σの語wを引数とし、２進数と解釈したときの値を返す関数 φ:Σ*→N > を帰納的に定義せよ。（ 0以外で先頭の0は無視し、 εに対する値は0 とする。）

語と数字を区別するため、語は""で囲むことにします。
また、語と語の連結を演算子・で表すとします。
例えばd = "id1"でe = "87"なら、d・e = "id187"です。

例えばですが、
「Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}とし、
Σの語wを引数とし、wを10進数と解釈した時の値を返す関数fを帰納的に定義せよ」
と聞かれたら、次のように答えれば良いと思います。

w = w'・d（ただしdは1文字の語）の時、
f(w) := 10f(w') + f(d)
f("0") := 0
f("1") := 1
f("2") := 2
f("3") := 3
f("4") := 4
f("5") := 5
f("6") := 6
f("7") := 7
f("8") := 8
f("9") := 9
（記号:=は「定義」を表すものとします）

こうすると例えばw = "29"の時、f(w)は次のように処理されます。
f(w)
= 10f("2") + f("9")　（f(w)において、w' = "2", d = "9"）
= 20 + 9　（定義よりf("2") = 2, f("9") = 9）
= 29

w = "295"の時、f(w)は次のように処理されます。
f(w)
= 10f("29") + f("5")　（f(w)において、w' = "29", d = "5"）
= 10{ 10f("2") + f("9") } + f("5")　（f("29")において、w = "2", d = "9"）
= 10(20 + 9) + 5
= 200 + 90 + 5
= 295

関数fの作り方は他にもあると思います。これは一例です。
別の方法で作れるなら、それを答えてもOKです。
結局のところ、私が作った例題で尋ねていることは
「とにかくどんな方法でもよいから、帰納的定義を使って関数fを作って下さい」
ということです。

質問者さんが取り組んでいる問題に関しても聞かれていることは同じだと思います。
「～～を証明して下さい」という問題ではなく、
「どんな方法でもよいから、再帰的定義を使って関数φを作ってください」という問題です。

ちなみに私は質問者さんの取り組んでいる分野にあまり詳しくありません。
なので的外れなことを言っているかもしれないので注意して下さい。