Solved

# Recursive Definition

Posted on 2011-10-19
204 Views
Give a recursive definition for the sex X of all binary strings with an even number of 0's

0
Question by:mustish1

LVL 37

Expert Comment

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 Comment

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

LVL 37

Expert Comment

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

LVL 37

Accepted Solution

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

LVL 26

Expert Comment

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

LVL 37

Expert Comment

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

## Featured Post

### Suggested Solutions

Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
This video discusses moving either the default database or any database to a new volume.