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