CMIMC 2018 Computer Science Problem 8

We consider a simple model for balanced parenthesis checking. Let \mathcal{R}=\{(()) \rightarrow \mathrm{A},(\mathrm{A}) \rightarrow \mathrm{A}, \mathrm{AA} \rightarrow \mathrm{A}\} be a set of rules for phrase reduction. Then the phrase is balanced if and only if the model is able to reduce the phrase to A by some arbitrary sequence of rule applications. For example, to show ((())) is balanced we can do:

((())) \rightarrow(\mathrm{A}) \rightarrow \mathrm{A} \quad \checkmark

Unfortunately, the above set of rules \mathcal{R} is not complete; find the number of balanced parenthetical phrases of length 14 for which \mathcal{R} is insufficient to show that they are balanced.