Question

Give a recursive algorithm for finding all balanced strings of parentheses containing n or fewer symbols.

\(\)

Short answer

Recursive algorithm has been found.

Step-by-step solution

Define recursive and reversal of the string

The recursive function is one that have its values at some specific points obtained by some previous points. Consider the example for the recursive function\({\bf{f}}\left( {\bf{k}} \right){\bf{ = f}}\left( {{\bf{k - 2}}} \right){\bf{ + f}}\left( {{\bf{k - 3}}} \right)\)is define over the non-negative integer.

The string is the set of numbers for example\(abcd\)is the string where all four variables can take up any values.

Consider the reversal \({w^R}\) of the string \(w\) is the string written in reverse order

Step 2: Recursive algorithm

The recursive algorithm for finding all balanced strings of parentheses containing\(n\)or fewer symbols:

Procedure generated (\(x\): non-negative integer):

If\(n\)is odd then

Begin

\(\begin{aligned}{l}S: &= S\left( {n - 1} \right)\\T: &= T\left( {n - 1} \right)\end{aligned}\)\(\left\{ {T \cup S{\rm{ is the set of balanced strings of length }}n} \right\}\)

End

Else

If\(n = 0\)then

Begin

\(\begin{aligned}{l}S: &= \phi \\T: &= \left\{ \lambda \right\}\end{aligned}\)

End

Else

Begin

\(\begin{array}{l}{T_1}: &= T\left( {n - 2} \right)\\{S_1}: &= S\left( {n - 2} \right)\\T: &= {T_1} \cup \left\{ {(a\} /a \in {T_1} \cup {S_1}\;and\;l\left( a \right) &= n - 2} \right\}\\S: &= {S_1} \cup \left\{ {ab/a \in {T_{1\;}}and\;b \in {T_1} \cup {S_1}\;and\;l\left( {ab} \right) &= n} \right\}\end{array}\)

End

\(\left\{ {T \cup S{\rm{ is the set of balanced strings of length }}n} \right\}\).

Hence, recursive algorithm has been found.