• Support PF! Buy your school textbooks, materials and every day products Here!

Recursive Definition

  • Thread starter sta|ker
  • Start date
  • #1
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
3,750
99
If [itex] \omega = 010 [/itex] then you just claimed that 001010100 is in A.
 
  • #3
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]
 

Related Threads on Recursive Definition

  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
3
Views
11K
Replies
6
Views
6K
Replies
0
Views
2K
Replies
5
Views
13K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
761
  • Last Post
Replies
6
Views
5K
Top