Recursive Definition of Well-Balanced Parentheses

[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.

 

[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

 

[EvLer]

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

 

[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.