Search code examples
recursioncomputer-sciencecomputer-science-theory

Recursive Definition for Language

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.

Solution

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