CA Rule — Finite State Transition Graph

This finite set of production rules completely specifies the infinite set Oi, which thus forms a regular language. 

We make four additional comments about figure 6.2-a  

Not all possible sequences of O s and I s appear in Oi. Since no path can include the sequence IIT, for example, all configurations 0i must exclude this particular block of sites. 

The graph g is not unique. An alternative, and simpler , finite STG (call it g) is shown in figure 6.2-b. It is obtained from g by deleting all of the equivalent nodes in g, where two nodes are defined to be equivalent if all paths passing through them carry exactly the same symbols. In our example, nodes q and 02 are equivalent and can thus be combined into a single node. 

Both g and g are non-deterministic, in the sense that multiple arcs originating from the same node carry the same symbol. A given word in the resulting formal language therefore need not originate from a unique path. 

---