Array Grammars

Array grammars are the analog to language grammars for two or higher dimensions. A language grammar consists of an alphabet, a start symbol, one or more terminal symbols and a set of re-writing rules called productions that create new sequences of symbols from the start symbol. An array grammar is similar, except that the productions create two-dimensional patterns on a grid instead of linear sequences.

The following is a simple example. The alphabet consists of the symbols a, b, and t. The start symbol is a and the terminal symbol is t. The rules are the following:

After a few applications of the rules, we can get the patterns:
 

							b
		a				t	b
	t	b			t	t	b
t	t	t		t	t	t	a

Array grammars were extensively studied by Azriel Rosenfeld in [Rosenfeld, 1979]. They are also related to Lindenmayer L-systems [Lindenmayer, 1968]. L-systems apply re-writing rules in parallel, something that is also done in array grammars. They were intended to be used to study plant growth and cell division and have resulted in many impressive examples [Prusinkiewicz and Lindenmayer, 1990].

Cellular Automata

Cellular automata have an even longer history. They were introduced by John von Neumann in the 1940s and described by Arthur Burks in [Burks, 1970]. There have been many articles and books on them, and John Conway's Game of Life has become a staple example in many programming courses.

A cellular automaton consists of a two dimensional grid that contains cells. These cells can be born or die, have a state that can change, and can communicate with their neighbors. Neighbors can either consist of the four contiguous cells in the grid or the eight that touch the cell. A state change in a neighbor can result in a state change in the cell itself.

Array Grammars that Generate Cellular Automata

The re-writing rules for an array grammar can be used to generate a cellular automaton. Each rule can generate one or more cells. Some of these cells can be 'terminal', in that they do not generate any further growth, while others can create new cells. As in real plant growth, cell creation is done in parallel.

It makes sense to avoid placing two cells in the same grid position. The little example above has this property. Several rules are applied at the same time, but they carefully avoid inserting two cells in the same spot. This puts a restriction on the design of the rules.

These rules are also context free. That means that only one symbol appears on the left-hand side of the rule. So each non-terminal symbol is re-written without reference to any symbols adjacent to it. As in linear languages, the study of context-free grammars is much simpler than that of context-sensitive ones. This paper only concerns context-free rules.

Once the growth rule that generates new cells has been applied, the cell can continue on as a member of the resulting cellular automaton. The growth rules can be supplanted by new rules. These can send messages to neighbors, receive messages and change the state of the cell. This can be used to simulate the growth and life of a plant.

Coordinate Systems

Rectangular coordinates are usually used for cellular automata, but other coordinate systems are available. A particularly attractive candidate is that of hexagonal coordinates. In a hexagonal system, there are three axes in the plane at 60 ^o angles to each other. This results in a hexagonal grid rather than a square one. A nice feature of a hexagonal cell is that the six adjacent cells all share a border with the cell. Also hexagonal cell packing is known to be efficient.

Neighbors in a hexagonal configuration can be denoted by the directions east, northeast, northwest, west, southwest, and southeast. So in the simple example above, cells would be placed at a 60^o angle to the parent cell rather than at a 45^o one. No cell would be directly above or below the parent cell, but it could be due east or due west.

The resulting pattern will be more pyramidal in appearance rather than strictly triangular. Notice that the center cell has six neighbors each sharing part of a common border.

Java Implementation

An array grammar generating a cellular automaton makes a nice programming example for students in a software design course, or even in an automata theory course. A Java applet or window provides a convenient graphical environment. Cells can be represented by small circles on a canvas, and the cell's state can be graphically shown by its color. Hexagonal coordinates provide a tight packing of the circles, so that the resulting picture resembles a real object.

Generation of new cells from an existing cell is appropriately done using Java threads. A growth rule can be installed in each cell upon its creation, and a thread can use this rule to generate a new cell. After a cell has been generated, it can be viewed as a member of the cellular automaton. It can be accessed through the grid, or it can be stored on a queue or list of cells for further activity.

Since each cell is placed into a grid, it can either generate new cells in neighboring locations or communicate with existing neighbor cells. This means that both the grid and grid directions have to be modeled. This provides a nice example of polymorphism, since each direction can be represented by a class derived from an abstract base class. Similarly, while all the rules are different, they all can be derived from a base rules class. All the thread has to know is that it must apply a growth rule. The specific rule stored in the cell can be a subclass of the growth rule class. Polymorphism will ensure that the correct rule is applied.

The graphics needed for this applet are quite simple. The cells can be represented by colored circles drawn on a canvas. Drawing each cell only requires knowledge of its center, radius and color. The center can be computed from the position of the cell in the automaton grid. The radius can be made a constant, and the color, which represents the cell's state, can be passed in from the cell.