2. Construction of Finite Time Sets

This section describes the construction of the set of configurations generated after a finite number of time steps of cellular automaton evolution, starting from the set of all possible configurations. It is shown that may be represented as a regular language (cf. [2, 16]), and an explicit construction of the minimal grammar for this language is given. Section 3 describes some properties of such grammars, and Sect. 4 discusses their form for a variety of cellular automata.

To describe the construction we begin with a simple example. The procedure followed may be generalized directly.

Consider the construction of the set generated by one time step in the evolution of the , cellular automaton with a local rule given by (``rule number 76'' [1])

The value of a site at position in a configuration depends on a neighbourhood of three sites in the preceding configuration . The adjacent site depends on the overlapping neighbourhood . The dependence of on associated with this two-site overlap in neighbourhoods may be represented by the graph of Fig. 2.1 (analogous to a de Bruijn graph [17]). The nodes in the graph represent the overlaps . These nodes are joined by directed arcs corresponding to three-site neighbourhoods. The local cellular automaton rule of Eq. (2.1) defines a transformation for each three-site neighbourhood, and thus associates a symbol with each arc of . Each possible path through corresponds to a particular initial configuration . The successor of each initial configuration is given by the sequence of symbols associated with the arcs on the path. The sequences of symbols obtained by following all possible paths through thus correspond to all possible configurations obtained after one time step in the evolution of the cellular automaton (2.1). The complete set may thus be represented by the graph . It is clear that not all possible sequences of 0's and 1's can appear in the configurations of . For example, no path in can include the sequence , and thus no configuration in can contain a block of sites 111.

[ Figure 2.1 ] The state transition graph for a non-deterministic finite automaton (NDFA) that generates configurations obtained after one time step in the evolution of the , cellular automaton with rule number 76 [Eq. (2.1)]. Possible sequences of site values are represented by possible paths through the graph. The nodes in the graph are labelled by pairs of initial site values; the arcs then correspond to triples of initial site values. Each such triple is mapped under rule number 76 to a particular site value. The graph with arcs labelled by these site values corresponds to all possible configurations obtained after one time step. Note that the basic graph is the same for all , cellular automata; only the images of the initial site value triples change from one rule to another.

The graph of Fig. 2.1 may be considered as the state transition graph for a finite automaton which generates the formal language . Each node of corresponds to a state of the finite automaton, and each arc to a transition in the finite automaton, or equivalently to a production rule in the grammar represented by the finite automaton. The set thus forms a regular language. Labelling the states in as , the productions in the grammar for this language are:

This finite set of rules provides a complete specification of the infinite set .

Each path through corresponds uniquely to a particular initial configuration . But several different paths may yield the same successor configuration . Each such path corresponds to a distinct inverse image of under . Enumeration of paths in shows, for example, that there are 5 distinct inverse images for the sequence 00 under the cellular automaton mapping (2.1), 5 also for 01 and 10, and 1 for 11.

The finite automaton of Fig. 2.1 is not the only possible one that generates the language . An alternative finite automaton is shown in Fig. 2.2, and may be considered ``simpler'' than since it has fewer states. is obtained from by combining the 00 and 10 nodes, which are equivalent in that only paths carrying the same symbol sequences pass through these nodes. The complete set of symbol sequences generated by the possible paths through is identical to that generated by possible paths through .

The finite automata and are non-deterministic in the sense that multiple arcs carrying the same symbol emanate from some nodes, so that several distinct paths may generate the same word in the formal language. It is convenient for many purposes to find deterministic finite automata (DFA) equivalent to the non-deterministic finite automata (NDFA) and . Such DFA may always be found by the standard ``subset construction'' (e.g. [6, 7]).

Consider for example the construction of a DFA equivalent to the NDFA of Fig. 2.1. Let be the set of all possible subsets of the set of nodes (the power set of ). There are elements of ; each potentially corresponds to a state in . The construction of begins from the ``start node'' . This node is joined by a 0 arc to the node corresponding to the set of NDFA states reached by a 0 arc according to (2.2) from any of the in . An analogous procedure is applied for each arc at each node in . The resulting graph is shown in Fig. 2.3, and may be represented by the productions

[ Figure 2.2 ] The state transition graph for an alternative NDFA that generates the language obtained after one time step of evolution according to rule 76. This NDFA is obtained by combining two equivalent states in the NDFA of Fig. 2.1.

[ Figure 2.3 ] The state transition graph for a deterministic finite automaton (DFA) obtained from the non-deterministic finite automaton of Fig. 2.1 by the subset construction [and represented by the productions of Eq. (2.3)]. Here and in other DFA graphs, the start node is shown encircled. Words in the regular language correspond to paths through , starting at .

Notice that only 5 of the 16 possible are reached by transitions from . The production in Eq. (2.3) yielding the null set (often denoted ) signifies the absence of an arc carrying the symbol 1 emanating from the node.

The DFA of Fig. 2.3 provides an alternative complete description of the language represented by the NDFA and of Figs. 2.1 and 2.2. Possible sequences of symbols in words of correspond to possible paths through , starting at . Consider the procedure for recognizing whether a sequence can occur in . If can occur, then it must correspond to a path through the NDFA , starting at some node. The set of possible paths through is represented by a single path through the DFA . The start state in corresponds to the set of all possible states in . As each symbol in the sequence is scanned, the DFA makes a transition to a state representing the set of states that could reach at that point. The sequence can thus occur in a word of if and only if it corresponds to a path in . The deterministic nature of ensures that this path is unique.

Complete cellular automaton configurations consist of infinite sequences of symbols, and correspond to infinite paths in the DFA graph . The possible words in may thus be generated by following all possible paths through .

Just as for the NDFA , some of the states in the DFA are equivalent, and may be combined. Two states are equivalent if and only if transitions from them with all possible symbols (here 0 or 1) lead to equivalent states. An equivalent DFA shown in Fig. 2.4 may thus be obtained by representing each equivalence class of states in by a single state. It may be shown that this DFA is the minimal one that recognizes the language [18, 6, 7]. It is unique (up to state relabellings), and has fewer states than any equivalent DFA. Such a procedure yields the minimal form for any DFA; the analogous procedure for NDFA does not, however, necessarily yield a minimal form.

In most cases, the minimal DFA that generates all (two-way) infinite words of a regular language is the same as the minimal DFA constructed above that recognizes all finite (or one-way infinite) sequences of symbols in words of the language. In some cases, such as that of Fig. 2.5 (the set for rule number 18), however, the latter DFA may contain additional ``transient'' subgraphs rooted at , feeding into the main graph. The set of infinite paths through these transient subgraphs is typically a subset of the set of infinite paths in the main graph.

The minimal DFA of Fig. 2.4 provides a simple description of the regular language . Regular expressions, mentioned in Sect. 1, provide a convenient notation for this and other regular languages. In terms of regular expressions,

where infinite repetition to form each infinite word is understood. Here represents an arbitrary number (possibly zero) of repetitions of the string , and stands for or .

[ Figure 2.4 ] The state transition graph for the minimal DFA that generates the regular language obtained after one time step of evolution according to cellular automaton rule 76. The graph is obtained by combining equivalent nodes in the DFA of Fig. 2.3. It has the smallest possible number of nodes.

[ Figure 2.5 ] The state transition graph for the minimal DFA corresponding to the regular language obtained after one time step in the evolution of cellular automaton rule 18. This graph contains a ``transient'' subgraph rooted at the start state, feeding into the main graph. All symbol sequences occurring at any point in a word of may be recognized as corresponding to paths through beginning at the start state. Complete words in may nevertheless be generated as possible infinite paths in , with the transient subgraph removed.

The example discussed so far generalizes immediately to show that the set of configurations generated by time steps of evolution according to any cellular automaton rule forms a regular language. Constructions analogous to those described above give grammars for these languages. The number of states in the initial NDFA is in general . (Two examples are shown in Fig. 2.6; graphs for successively larger values of may be obtained by a recursive construction [17].) The size of the DFA obtained from by the subset construction may be as large as , but is usually much smaller. (Note that the ``reject'' state is not counted in the size of the grammar.)

As an example, consider the language generated by two time steps in the evolution of the cellular automaton (2.1). The original NDFA which corresponds to this language has 16 states, and the DFA obtained from it by the subset construction has nine states. Nevertheless, the resulting minimal DFA has just three states, and is in fact identical to that found for as shown in Fig. 2.4. Since gives a complete (finite) specification of the languages , this implies that

in this case. is thus the limit set for the evolution of the cellular automaton of Eq. (2.1).

previous  l  next