CONTEXT-SENSITIVITY OF TWO-DIMENSIONAL REGULAR ARRAY GRAMMARS

Regular array grammars (RAGs) are the lowest subclass in the Chomsky-like hierarchy of isometric array grammars. The left-hand side of each rewriting rule of RAGs has one nonterminal symbol and at most one “#” (a blank symbol). Therefore, the rewriting rules cannot sense contexts of non-# symbols. However, they can sense # as a kind of context. In this paper, we investigate this #-sensing ability, and study the language generating power of RAGs. Making good use of this ability, we show a method for RAGS to sense the contexts of local shapes of a host array in a derivation. Using this method, we give RAGs which generate the sets of all solid upright rectangles and all solid squares. On the other hand, it is proved that there is no context-free array grammar (and thus no RAG) which generates the set of all hollow upright rectangles.