hello. this is a discrete math/computer science problem. i have absolutely no id

Question

hello. this is a discrete math/computer science problem. i have absolutely no idea what this question even means..the picture on the top is the actual problem and in the bottom is what my instructor told us he wants us to find. even after he explained it i still dont know where to start. can you help me out here? thanks Consider the following inductive definition of a composed bit string of O's and 1's. Foundation: The empty bit string is a composed bit string. Constructor: If s and t are composed bit strings, then so are Os1t and 1sOt. Part a: List the composed bit strings that can be creatèd with just one application of the constructor rule Part b: List the composed bit strings that can be created by applying the constructor rule to bit strings that can be created with one or zero applications of the constructor rule. (Hint: there are 16 distinct bit strings.) See clarification on Piazza e regarding what is being asked for Part c: Use structural induction to show that every composed bit string consists of an equal number of O's and 1's. Make sure to indicate what P(n) is (i.e., the predicate you are proving holds true for all natural numbers n)

Explanation / Answer

By the Foundation S0 = { z } where z is an empty string

a) By appying constructor to above set we get strings 0s1t when s,t are z this gives string 0z1z = 01 (z is an empty string)

similarly 1s0t results 1z0z = 10

So S1 = {01, 10}

b) By application of constructor on S0 U S1 = {z, 01, 10)

when t=z and s can be z, 01, 10 this results following strings for 0s1t

{ 0z1z, 0011z, 0101z } = {01, 0011, 0101 }

t = 01, and s in z, 01, 10 results = {0z101, 001101, 010101 } = {0101, 001101, 010101 }

t =10 and s in z, 01, 10 results = {0z110, 001110, 010110 } = {0110, 001110, 010110 }

Similarly for string 1s0t

when t=z and s can be z, 01, 10 this results = {10, 1010, 1100 }

when t=01, and s in z, 01, 10 results ={ 1001, 101001, 110001 }

when t=10, ans s in z, 01, 10 results = { 1010, 101010, 110010 }

So total set S2 ={01, 10, 1010, 1100, 1001, 0110, 0011, 0101 , 001101, 010101, 001110, 010110, 101001, 110001, 101010, 110010}

c)

Let p(n) be "The composed bit string of length n consists equal number of 0s and 1s"

conside base case when n=0,

p(0) consists equal number of 0s and 1s, this is true as empty string contains 0 number of 1s and 0s.

hypothesis:

Let p(n) where n<=k is also true that is composed bit string of length <=k contains equal number of 0s and 1s.

Induction case: consider p(n) for n >k

there only two ways to create a composed bit string of length n>k, that is with 0s1t and 1s0t where s,t are composed bit strings of length <=k.

From hypothesis we have s, t contains equal number of 0s and 1s, so 0s1t and 1s0t will also contain equal number of 0s and 1s.

So if p(n) is true for n<=k then p(n) is also true for n>k.

Now from structural induction and proof of base case every composed bit string contains equal number of 0s and 1s.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.