Generalized parenthesis languages and minimization of their parenthesis parts (Q800093)

Let I be an alphabet. We call \(\hat I=I\cup\bar I\) a set of parentheses when \(\bar I=\{\bar a| a\) is in \(I\}\) is a bijective image of I and is disjoint from I. Let K be an alphabet that possibly includes a set of parentheses \(\hat I\), and \(G=(N,K,P,S)\) be a context-free grammar (cfg, for short) such that the production rules in P are of the form \(A\to au\bar aB, A\to bB\) or \(A\to e,\) where A and B are in the nonterminal alphabet N, a is in I, u is a word over \(N\cup K\) not containing symbols in \(\hat I\), and b is in \(K-\hat I.\) The symbol e stands for the empty word. By extending the concept of parenthesis language, one of the authors (M. Takahashi) called, in a previous paper, G a generalized parenthesis grammar over K with the part \(\hat I\) (a (K,L)-gpg, for short) and the language generated thereby a generalized parenthesis language over K with parenthesis part \(\hat I\) (a (K,I)-gpl, for short). The authors proved in this paper the following nice mathematical features of the gpg's: For a given regular set L over K and a set \(\hat I\) of parentheses in K, one can decide whether L is a (K,I)-gpl or not. The regularity problem for gpl's is decidable (direct proof). For a given (K,I)-gpg G and a subset I' of I it is decidable whether L(G) is a (K,I')-gpl or not (thus the parenthesis part of a given gpl can be minimized). It is undecidable whether a cfg generates a gpl or not, this result being in contrast with the case of parenthesis languages.