At each step, the rule then specifies that the string which exists at that step should be scanned from left to right, and the first sequence BA that is found should be replaced by ABA . In the picture, the black dots indicate which elements are being replaced at each step. In the case shown, the initial string is BABA .

In all cases, the systems are started from the initial string BAB . The black dots indicate the elements that are replaced at each step.

Thus for example the state of a substitution system at a particular step can be represented by the string ABBBABA , where the A 's correspond to white elements and the B 's to black ones. The substitution systems that we discussed in the previous section work by replacing each element in such a string by a new sequence of elements—so that in a sense these systems operate in parallel on all the elements that exist in the string at each step. … And this setup is now directly analogous to the search-and-replace function of a typical text editor.

The rules for the multiway system can then be given for example as {"AAB"  "BB", "BA"  "ABB"} The evolution of the system is given by the functions MWStep[rule_List, slist_List] := Union[Flatten[ Map[Function[s, Map[MWStep1[#, s] &, rule]], slist]]] MWStep1[p_String  q_String, s_String] := Map[StringReplacePart[s, q, #] &, StringPosition[s, p]] MWEvolveList[rule_, init_List, t_Integer] := NestList[MWStep[rule, #] &, init, t] An alternative approach uses lists instead of strings, and in effect works by tracing the internal steps that Mathematica goes through in trying out possible matchings. With the rule from above written as {{x___, 0, 0, 1, y___}  {x, 1, 1, y}, {x___, 1, 0, y___}  {x, 0, 1, 1, y}} MWStep can be rewritten as MWStep[rule_List, slist_List] := Union[Flatten[Map[ReplaceList[#, rule] &, slist], 1]] The case shown on page 206 is {"AB"  "", "ABA"  "ABBAB", "ABABBB"  "AAAAABA"} starting with {"ABABAB"} . Note that the rules are set up so that a string for which there are no applicable replacements at a given step is simply dropped.

Such systems in general take a string of elements and at each step replace blocks of these elements with other elements according to some definite rule. … The substitution system works by replacing blocks of elements at each step according to the rule shown.

Substitution systems in which all replacements are done that are found to fit in a left-to-right scan can be implemented as follows GSSEvolveList[rule_, s_, n_] := NestList[GSSStep[rule, #] &, s, n] GSSStep[rule_, s_] := g[rule, s, f[StringPosition[s, Map[First, rule]]]] f[{ }] = { }; f[s_] := Fold[If[Last[Last[#1]] ≥ First[#2], #1, Append[#1, #2]]&, {First[s]}, Rest[s]] g[rule_, s_, { }] := s; g[rule_, s_, pos_] := StringReplacePart[ s, Map[StringTake[s, #] &, pos] /. rule, pos] with rules given as {"ABA"  "BAAB", "BBBB"  "AA"} .

In this case, the evolution can be obtained using SSEvolveList[rule_, init_String, t_Integer] := NestList[StringReplace[#, rule]&, init, t] For a neighbor-dependent substitution system such as the first one on page 85 the rule can be given as {{1, 1}  {0, 1}, {1, 0}  {1, 0}, {0, 1}  {0}, {0, 0}  {0, 1}} And with this representation, the evolution for t steps is given by SS2EvolveList[rule_, init_List, t_Integer] := NestList[Flatten[Partition[#, 2, 1] /. rule]&, init, t] where the initial condition for the first example on page 85 is {0, 1, 1, 0} .

Conditions for convergence [in string rewriting] One way to guarantee that there is convergence after one step is to require as in the previous section that blocks to be replaced cannot overlap with themselves or each other. … Much as in the previous section, even if paths do not converge for every possible string, it can still be true that paths converge for all strings that are actually generated from a particular initial string.

Sequence equations One can ask whether by replacing variables by sequences one can satisfy so-called word or string equations such as Flatten[{x, 0, x, 0, y}]  Flatten[{y, x, 0, y, 1, 0, 1, 0, 0}] (with shortest solution x = {1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0} , y = {1, 0, 1, 0, 0, 1, 0, 1, 0, 0} ).

And by using rules such as s[x___, 1, 0, y___]  {s[x, 0, 1, 0, y], Length[s[x]]} one can keep track of the positions at which substitutions are made. ( StringReplace replaces all occurrences of a given substring, not just the first one, so cannot be used directly as an alternative to having a flat function.)