Recursive Definitions

[tragicallylost]

Hi. I have a problem where I have to give a recursive definition for the set of all binary strings containing an odd number of 0s.

I don't have a clue on how to start this. I know that there are two parts to a recursive definition. I am stuck on the first part. If someone could just give me a push in the direction to start this, I would appreciate it GREATLY!!

 

[daon]

Hi. I have a problem where I have to give a recursive definition for the set of all binary strings containing an odd number of 0s.

I don't have a clue on how to start this. I know that there are two parts to a recursive definition. I am stuck on the first part. If someone could just give me a push in the direction to start this, I would appreciate it GREATLY!!

Is this a class in Automata? I THINK these work, but theres a possibility I left something out:

Here's a way with a Context Free Grammar:

\(\displaystyle S->SAS,0,01,10,1 \\
A->01,10,0\)

Here's a Regular Expression (and, hence, an outfile for a FSM):

\(\displaystyle [0*10*10*]*10*\) \(\displaystyle \cup\) \(\displaystyle [1*01*01*]*01*\)

 

[tragicallylost]

Hi. Thanks, but I have no idea what you did. The book doesn't use that kind of notation. Here's an example to show what the recursive definition looks like according to the text:

Give a recursive definition for multiplication of 2 positive integers m and n.

1) m(1)=m
2) m(n) = m(n-1) + m for n >=2

Thanks again though.

 

[daon]

Hi. Thanks, but I have no idea what you did. The book doesn't use that kind of notation. Here's an example to show what the recursive definition looks like according to the text:

Give a recursive definition for multiplication of 2 positive integers m and n.

1) m(1)=m
2) m(n) = m(n-1) + m for n >=2

Thanks again though.

Okay, thats well and fine, but your question above is not strictly numerical in nature. Once you mention "String" you are delving into the theory of languages, at least in my mind.

You want a formula that represents all possible strings containing an odd number of zeros, right? The problem is that you have a choice for S(1) and S(n), and whatever you choose, you'll be leaving things out. I may be thinking along the wrong lines though.

One thing to notice is that 2 to any odd power gives an odd number of zeros. Maybe you can work with that? Hopefully someone else here will be more of help.

 

[pka]

This is almost impossible to explain. So please read very carefully.
Let B(N) be the number of bit strings of length N with an odd number of zeros.
B(1)=1; 0
B(2)=2; 01,10
B(3)=4; 011,101,110,000.

To get B(4) we take any string in B(2) first add two zeros to before or after the we add two ones before or after. That gives us B(4)=8. To get B(5) we do the same thing to B(3). Thus B(5)=4*B(3).

So now if N>3 then B(N)=4*B(N-2).

 

[daon]

Was the question asking for the cardinality?

Also, with your formula, it seems also that B(N)=2*B(N-1), or B(N)=\(\displaystyle 2^{N-1}\).

Which is kind of cool, and I wonder if it is related at all to the following:
\(\displaystyle \L \frac{1}{2} \sum _{k=0}^n {n \choose k} \,\, = \,\, 2^{n-1}\)

 

[pka]

Was the question asking for the cardinality?

Yes, this kind of problem is quite common in Discrete Mathematics courses.
Johnsonbaugh’s book has a good many of these sorts. In fact, that is where I found that poor description I tried to give above.

I knew the answer gotten another way:

\(\displaystyle \L B(N) = \sum\limits_{k = 1}^{\left\lceil {\frac{N}{2}} \right\rceil } {\left( {\begin{array}{c}
N \\
{2k - 1} \\
\end{array}} \right)}\).

Just all the odd occurrences.