# Recursive Definition

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

###### Who is Participating?

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

Commented:
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

Author 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

Commented:
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

Commented:
>> 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

Commented:
Okay. I get it now d-glitch. It's the same type of problem, but they handle it different ways.
0