Consider words made out of the characters \'(\" and \')\'. Say such a word is va

Question

Consider words made out of the characters '(" and ')'. Say such a word is valid if it is correctly parenthesized in the sense that every open parenthesis has a matching close parenthesis somewhere after it. For example (()(())) is valid but )()( is not. We also consider the empty word to be valid. Write out all the valid words of length 2, 4, and 6. Show that every nonempty valid word can be written uniquely in the form (A)B where A and B are valid words (possibly empty). Let w(n) be the number of valid Words of length 2n. Show that for n 1, where w(0) = 1.

Explanation / Answer

Each word of size 2n has n '( ' and n ')'. each word is of form
w -> (w)
or
w -> (w)w
or
w-> empty

Thus concentrate on the second rule.
we have total of n pairs out of which is is used and n-1 are resursively used.
Suppose k are in the first word and n-k-1 in the second. The iterating over all possible values of k, we have,
W(n) = w(k)(for first recursion) * w(n-k-1)(for second recursion)

Other cases are included in the same.

We must remove one pair per iteration and not keep it as w(k) * w(n-k) because it leads to a large no of repeated cases.

look into uses of catalan number for more help.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.