Recursive Definition

  • Thread starter sta|ker
  • Start date
  • #1
sta|ker
12
0

Homework Statement


Give a recursive definition for the set
of bit strings [itex]\{ 0^{r} 1^{s} 0^{r} \| r, s \in N \}[/itex]. Note the number of 0’s must be equal, but the
number of 1’s may be different from the number of 0’s.

Homework Equations


N/A

The Attempt at a Solution


I believe this is:
Basis: [itex]\lambda \in A[/itex]
Recursive Step: If [itex]\omega \in A[/itex], then [itex]0 \omega 1 \omega 0 \in A[/itex]

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

Thanks!
 

Answers and Replies

  • #2
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
2021 Award
5,223
1,178
If [itex] \omega = 010 [/itex] then you just claimed that 001010100 is in A.
 
  • #3
sta|ker
12
0
If [itex] \omega = 010 [/itex] then you just claimed that 001010100 is in A.

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

Basis: [itex]0 1^{n} 0 \in A , n \in N[/itex]
Recursive Step: if [itex]w \in A[/itex], then [itex]0 w 0 \in A[/itex]

Because, this would give: [itex]A = \{ 010, 00100, 001100, ... \}[/itex]
 

Suggested for: Recursive Definition

  • Last Post
Replies
3
Views
368
Replies
2
Views
312
Replies
13
Views
658
Replies
4
Views
338
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
7
Views
814
  • Last Post
Replies
4
Views
471
  • Last Post
Replies
3
Views
603
Replies
7
Views
341
Top