Recursive Definition for Language

Question

Suppose I have a language consisting of just balanced parentheses, i.e., {ε, ( ), ( ( ) ), ( ) ( ), ( ( ( ) ) ), ( ( ) ( ) ), ... } and I'm asked to write a recursive definition for it. Could somebody give me an example of what that could look like? - I'm a bit new to this type of computer science theory.

Answer 1

A kind of recursive definition is grammar. To generate language of balanced parentheses :

S --> (S) | SS | ^

this is recursive because S appears in RHS of production rules.

production rules: LHS --> RHS

EDIT

Why (s) not S ?

because to add () pairs recursively and more then one time.

S --> (S) --->  ((S))   

in second step inner S is replaced by (S).

Answer 2

TEXT ::= BRACES | BRACKETS | LIST;
BRACES ::= "{" ( TEXT | /* nothing */ ) "}";
BRACKETS ::= "(" ( TEXT | /* nothing */ ) ")";
LIST ::= ( BRACES | BRACKETS ) | ( BRACES | BRACKETS ) "," LIST;