03876625

j

03876625 Yamasaki, Hideki Takahashi, Masako Generalized parenthesis languages and minimization of their parenthesis parts. Theor. Comput. Sci. 31, 1-11 (1984). 1984 Elsevier Science Publishers, Amsterdam EN decidability generalized parenthesis grammar generalized parenthesis language regular set

doi:10.1016/0304-3975(84)90121-X

Let I be an alphabet. We call $\hat I=I\cup\bar I$ a set of parentheses when $\bar I=\{\bar a\vert 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. R.Andonie