Recursive Definition

Give a recursive definition for the sex X of all binary strings with an even number of 0's

mustish1Asked:
Who is Participating?
 
TommySzalapskiConnect With a Mentor Commented:
So starting with a single X (we used S) you can build any string with an even number of 0s following those rules
B1. lamda is in X.  -- You can replace any X with nothing (lambda)
B2. 1 is in X.  -- You can replace any X with a 1
R1. If x is in X, so is 0x0.  --  You can replace any X with 0X0
R2. If x and y are in X, so is xy. (Answer may vary.)  --  You can replace any X with XX (you don't need a Y symbol here which is why it says answer may vary, I suppose.)
0
 
TommySzalapskiCommented:
I don't get what the "sex X" part is, but it's fairly simple to recursively determine if a string has an even number of 0s.
You just look at the first binary digit and if it's a 0 flip to false (or true if you are already at false) and keep going, if it's a 1 just keep going.

Since this appears to be an academic question, I'll wait for your reply before giving any more detail.
0
 
mustish1Author Commented:
I have answer but i dont get the question

B1. lamda is in X.
B2. 1 is in X.
R1. If x is in X, so is 0x0.
R2. If x and y are in X, so is xy. (Answer may vary.)
0
Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
TommySzalapskiCommented:
Oh. I get it now. I've seen that type of problem but it looks a little different.

I would just define it this way
X -> XX or 1 or 0X0 or lambda

So you can use that to build any binary string with an even number of 0s.
For example 10010110
X
XX  :  X->XX
1X  :  X->1
1XX    :  X->XX
10X0X  :  X->0X0
100X  :  X->lambda
100XX  : x->XX
1001X  : x->1
10010X0  : x->0X0
10010XX0  :  x->XX
10010110  :  x->1 (twice)
0
 
d-glitchCommented:
>> set X of all binary strings with an even number of 0's

Little x is a member of set Big X.

Does lambda mean the null/empty set?  Probably, but I am not sure.

This definition is a recipe for generating all possible members of X.
So you can't ever replace X with anything.
You can substitute previously generated members of the set into for x and y in R1 and R2 to extend the set.
You definitely do need the concatenate rule.

B1  =>  NULL
B2 =>     1

B1 + R1  =>   00    =>   0000
B2 + R1  =>   010  =>   00100

R2 lets you concatenate.
0
 
TommySzalapskiCommented:
Okay. I get it now d-glitch. It's the same type of problem, but they handle it different ways.
0
All Courses

From novice to tech pro — start learning today.