Regular language

Chapter 6 is a short primer on CA and language theory, and provides a basic discussion of formal language theory, the relationship between CA and formal language theory, power spectra of regular languages and reversible computation. 

We shall extensively employ the notation of graph theory it provides a powerful and elegant formalism for the description of both the structure of the discrete lattices on which the CA live, and the complete dynamics (he. the global state transitions) induced by those structures. Graph theory also allows the correspondence between CA configurations and the words of a regular language to be made in a very natural fashion. 

The grammars for regular languages can be conveniently specified by finite state transition graphs for the finite automata that recognize them. The vertices of the graph represent the the system states Cj E and the arcs represent the possible input states Uj A. The arrows point to the next state that will result from the initial state when the input on the arc is applied. 

While Wolfram [wolf84a] showed (and, as we will summarize below, made quite a few interesting deductions from the fact) that is a regular language for all... 

Regular Languages allow only those productions that are of the form a —> era or a —> (T. Recognized by Finite Automata. 

Below we present evidence that (1) the infinite-time limit sets of class cl and c2 CA form regular languages, (2) the infinite-time limit set of class c3 CA (appear to) form context-sensitive languages and (3) the infinite-time limit set of class c4 CA (appear to) to form unrestricted languages. While the evidence is very strong that the assertions about the infinite time limit sets of class c3 and c4 CA are in fact correct, a formal proof has yet to be provided. 

Fig. 6.1 Finite State Transition graph (STG) for the regular language C = jol" ...

We begin this section by showing that the finite-time limit set of an arbitrary CA rule ((>, Clf = (equation 6.2), is a regular language for all t To this... 

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

Table 6.2 Number of nodes Ht, C = 0,.. . 4 in the minimal deterministic state transition graph (DSTG) representing the regular language r2t[0, where 0 is an elementary fc = 2, r = 1 CA rule Amax is the maximal eigenvalue of the adjacency matrix for the minimal DSTG and determines the entropy of the limit set in the infinite time limit (see text), Values are taken from Table 1 in [wolf84a. ...

EXAMPLE Consider a simple but non-trivial STG consisting of two nodes and three arcs (the reader can check that this regular language actually characterizes the attractors of many one dimensional CA - rules R12, R56 and 162, among others) ... 

Ievine92] Levine L., Regular language invariance under one-dimensional cellular automaton rules, Complex Systems 6 (1992) 163-178. 

H87] Li, W., Power spectra of regular languages and cellular automata . Complex Systems 1 (1987), 107-130. 

To get the value language L(S) from (L (S)) one reverses the words and erases the sequence of 0 s and 1 s indicating the outcome of tests for a given interpretation. The families of context-free, of linear, and of regular languages are all closed under reversal and erasing so we have at once ... 

If the weights are integers, the neurons may assume binary activation values only and the network accepts a regular language [155]. 

This is the same as saying 4(H s) + 2(0 s) -> 4(H s) + 2(0 s). In regular language, the equation now says when four atoms of hydrogen unite with two atoms of oxygen, two molecules of water result. Think about this for a while and see if you can explain how and why the equation is now balanced. 

We have described the activity of a finite automaton which accepts the infinite regular language of the general configurations types (of the configurations of the observed machine TM). They are the words of the infinite length and having the form... 

---