Question

A Bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string. Give a recursive definition for the set of bit strings { 0r1s0r | r, s ∈ ℕ } . Note the number of 0’s must be equal, but the number of 1’s may be different from the number of 0’s.

Answer 1

r,s are elements of the naturals or {0,1} ?

Answer 2

yes

Answer 3

I am sorry. one second.

Answer 4

{ 0^r1^s0^r | r, s ∈ ℕ }

Answer 5

Ok that actually makes more sense

Answer 6

{ 0^r1^s0^r | r, s E N }

Answer 7

{ 0^r1^s0^r | r, s is element of Natural numbers }

Sorry I couldnt figure out how to use the symbol.

Answer 8

\[{ 0^r1^s0^r | r, s \epsilon \mathbb{N} }\]

Answer 9

Why close this? I think I prefer it open so more people can jump because I'm actually still thinking .

Answer 10

Well let's just think about the sequence \[f(r,s)=0^r 1 ^s 0^r ; r,s \in \mathbb{N} \\ f(1,1)=010 \\ f(1,2)=0110 \\ f(2,1)=00100 \\ f(2,2)=001100 \\ f(3,1)=0001000 \\ f(3,2)=00011000 \\ f(3,3)=000111000 \\ f(1,3)=01110 \\ f(2,3)=0011100 \\ \]
... so we are to think of a recursive form for this...

Answer 11

Well this doesn't answer the question...but we can find the lenth
\[|f(1,1)|=2(1)+1 \\ |f(1,2)|=2(1)+2 \\ |f(2,1)|=2(2)+1 \\ |f(2,2)|=2(2)+2 \\ |f(3,1)|=2(3)+1\\|f(3,2)|=2(3)+2\]
I hope you see a pattern and kind find the length of something more general like:
\[|f(m,n)| \text{ where } m,n \in \mathbb{N} \]