# Recursive definition

1. Jul 10, 2006

### EvLer

Can someone check this problem, please?

problem:
give a recursive definition for the set of strings of well-balanced parentheses:

my solution:
1. a set of single parentheses ()
2. nesting of strings already in the set
3. any concatenation of the strings already in the set

thanks in advance.

2. Jul 10, 2006

### 0rthodontist

Well, this is alright except for 2. What exactly is a "nesting of strings already in the set"? You have be more specific. You can make it more formal by saying
1. () is in the set
2. if B is in the set, then __ is in the set
3. if A and B are in the set, then AB is in the set

3. Jul 10, 2006

### EvLer

do I just say "(B)", i was not sure that is "formal" enough.

4. Jul 10, 2006

### 0rthodontist

Sure, that's plenty formal. It means that if the string B is in the set, then if you concatenate the strings (, B, and ), the result will also be in the set.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook