a. give a recursive definitions of the function ones(s), which counts the number of ones in a bit string s

b. use structural induction to prove that ones(st) = ones (s) + ones (t)

Printable View

- July 28th 2007, 08:13 AMDiscreterecursive definitions
a. give a recursive definitions of the function ones(s), which counts the number of ones in a bit string s

b. use structural induction to prove that ones(st) = ones (s) + ones (t) - July 28th 2007, 11:02 AMCaptainBlack
- July 29th 2007, 08:02 AMDiscrete
Does the concatenation operator here means add? I don't really get it though

- July 29th 2007, 09:51 AMCaptainBlack
- July 30th 2007, 07:33 AMDiscrete
But then if you just concatenate the string how will we be able to find the ones in a string??

- July 30th 2007, 09:11 AMCaptainBlack
Let s="100110"

ones(s) = ones("10011"|"0") = ones("10011")

.......... = ones("1001"|"1") = ones("1001") + 1

.......... = ones("100"|"1") + 1 = ones("100") + 1 + 1 = ones("100") + 2

.......... = ones("10"|"0") + 2 = ones("10") + 2

.......... = ones("1"|"0") + 2 = ones("1") + 2 = 1 + 2 = 3

RonL - July 31st 2007, 08:32 PMDiscrete
so the suggested algorithm here is that we start from the beginning of the string and separate a single string from the back and check if it's a one or zero, if it's a one then we add one right?

- July 31st 2007, 10:31 PMCaptainBlack
- August 1st 2007, 04:07 PMDiscrete
so what's the base case here? how do I proof part b by using structural induction??

- August 1st 2007, 08:38 PMCaptainBlack
The base case is that for all bit strings s and bit strings b of length 1:

ones(s|b) = ones(s) + ones(b)

Then suppose it true for all bit strings s and all bit strings b of length k or less. Then:

ones(s|b)=ones(s)+ones(b)

and so if b'=b|"0":

ones(s|b') = ones((s|b)|"0")=ones(s|b)+0 = ones(s)+ones(b)

and if b*=b|"1":

ones(s|b*) = ones((s|b)|"1")=ones(s|b)+1 = ones(s)+ones(b)+1=ones(s)+ones(b|"1")=ones(s)+ones (b*).

Hence it true for all bit strings s and all bit strings b of length k+1 or less.

Therefore by induction we may conclude that it is true for all bit strings s and b.

RonL - August 1st 2007, 09:21 PMDiscrete
what does b', b* means??

so there are two base case here? - August 1st 2007, 10:50 PMCaptainBlack
They mean what I defined them to be b' is b concatenated with "0" and b* is b concatenated with "1" , and these are part of the inductive step.

The base case was what I said it was:

Quote:

The base case is that for all bit strings s and bit strings b of length 1:

ones(s|b) = ones(s) + ones(b)

RonL

RonL