recursion - Recursive Definition for Language -

recursion - Recursive Definition for Language -

suppose have language consisting of balanced parentheses, i.e., {ε, ( ), ( ( ) ), ( ) ( ), ( ( ( ) ) ), ( ( ) ( ) ), ... } , i'm asked write recursive definition it. give me illustration of like? - i'm bit new type of computer science theory.

a kind of recursive definition grammar. generate language of balanced parentheses :

s --> (s) | ss | ^

this recursive because s appears in rhs of production rules.

production rules: lhs --> rhs

edit

why (s) not s ?

because add together () pairs recursively , more 1 time.

s --> (s) ---> ((s))

in sec step inner s replaced (s).

recursion computer-science computer-science-theory