Exercise 3:

Context-free description for the well-parenthesized words over {(,)}\{ ( , ) \} with no occurrence of ((((((
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 ()λ()\to\lambda.
Authors: Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.