# Recursive Definition

1. Oct 21, 2013

### sta|ker

1. The problem statement, all variables and given/known data
Give a recursive definition for the set
of bit strings $\{ 0^{r} 1^{s} 0^{r} \| r, s \in N \}$. Note the number of 0’s must be equal, but the
number of 1’s may be different from the number of 0’s.

2. Relevant equations
N/A

3. The attempt at a solution
I believe this is:
Basis: $\lambda \in A$
Recursive Step: If $\omega \in A$, then $0 \omega 1 \omega 0 \in A$

I just want to verify if this is correct or not.

Thanks!

2. Oct 21, 2013

### Office_Shredder

Staff Emeritus
If $\omega = 010$ then you just claimed that 001010100 is in A.

3. Oct 22, 2013

### sta|ker

Ohh, I think I see. $w$ represents the initial value, which would basically make everything I put wrong. What about the following:

Basis: $0 1^{n} 0 \in A , n \in N$
Recursive Step: if $w \in A$, then $0 w 0 \in A$

Because, this would give: $A = \{ 010, 00100, 001100, ... \}$