Recursive Definition

Homework Statement

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.

N/A

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!

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

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

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, ... \}$