Give a context-free description for the language
of the well-parenthesized words over
{(,)} with no occurrence of
(((.
For example,
()(()) and
(((()()))) are well-parenthesized
words, whereas
)( and
(() are not. Nevertheless,
(((()()))) is not valid since it has occurrences of
(((.
One way to define more precisely the language of well-parenthesized
words over
{(,)} is to describe it
as the set of words that can be reduced to the empty word by
successive applications of the rewrite rule
()→λ.