Hexagonal Array Grammar System

Abstract

In 1995, J.Dassow, R.Freund, and G.Paun extended the concept of cooperating grammar system in string case to array grammars by introducing cooperating array grammar system in rectangular grids [1]. Motivated by the fact that, hexagonal arrays on triangular grid can be treated as two dimensional representation of three dimensional blocks, we extended the result of [1] to hexagonal pictures by de ning hexagonal array grammar system. Context-free and regular hexagonal array grammars are two special classes of these grammars and we have made studies regarding the power of cooperation in case of hexagonal array grammars. Different types of hexagonal array grammar systems are defined and the generative capacities of these grammar systems are compared according to the number of components and modes of derivation. We observed that the difference in the generative capacity is based on the fundamental difference between regular and context free array grammars.