({{, (RefLink[SubstitutionSystem, paclet:ref/SubstitutionSystem])[rule,init,t] 
generates a list representing the evolution of the substitution system with the specified rule from initial condition init for t steps.}, {, (RefLink[SubstitutionSystem, paclet:ref/SubstitutionSystem])[rule,init]
gives the result of evolving init for one step.}, {, (RefLink[SubstitutionSystem, paclet:ref/SubstitutionSystem])[rule]
is an operator form of (RefLink[SubstitutionSystem, paclet:ref/SubstitutionSystem]) that corresponds to one step of evolution. }})

OpenersNotesSection(Spacer1)Details

In (RefLink[SubstitutionSystem, paclet:ref/SubstitutionSystem])[rule,…], rule can be of the following forms:

In list substitution systems, the (Subscript[rhs, i]) can be lists of any length or can be rectangular arrays of any depth but all with the same dimensions. They can also be individual elements such as integers.

In string substitution systems, the (Subscript[rhs, i]) can be strings of any length.

Both lists and string substitution systems can have rules that involve patterns, but every object that appears in the (Subscript[rhs, i]) must have a transformation defined by the rules given.

List substitution systems work with (RefLink[SparseArray, paclet:ref/SparseArray]) objects.

In string substitution systems, the initial condition init must be a string; in list substitution systems, it must be an array whose depth is equal to the depth of the (Subscript[rhs, i]).

In (RefLink[SubstitutionSystem, paclet:ref/SubstitutionSystem])[rule,init,tspec], the time specification tspec can have any of the following forms:

OpenersPrimaryExamplesSection(Spacer1)Examples  (26)

OpenersExampleSection0(Spacer1)Basic Examples  (3)

Five steps of a string substitution system:

SubstitutionSystem[{"A"->"AB","B"->"A"},"A",5]

Analogous substitution system with lists:

SubstitutionSystem[{0->{0,1},1->{0}},{0},5]

Steps in a 2D substitution system:

ArrayPlot/@SubstitutionSystem[{1->{{1,0},{1,1}},0->{{0,0},{0,0}}},{{1}},4]

Give the fourth step only:

ArrayPlot/@SubstitutionSystem[{1->{{1,0},{1,1}},0->{{0,0},{0,0}}},{{1}},{4}]

Alternative form:

ArrayPlot/@SubstitutionSystem[{1->{{1,0},{1,1}},0->0},{{1}},{4}]

Generate a rule icon for a substitution system:

RulePlot[SubstitutionSystem[{1->{{1,0},{1,1}},0->{{0,0},{0,0}}}]]

OpenersExampleSection1(Spacer1)Scope  (16)

OpenersExampleSubsubsection0(Spacer1)1D List Substitution Systems  (3)

SubstitutionSystem[{0->{0,1},1->{1,0}},{0},3]

Lists do not have to be the same length:

SubstitutionSystem[{0->{0,1},1->{0}},{0},3]

The initial condition can be of any length:

SubstitutionSystem[{0->{0,1},1->{1,0}},{0,1,0},3]

Rules can involve patterns:

SubstitutionSystem[{0|1->{1,2},2->{0,1}},{0},3]

SubstitutionSystem[{n_:>Range[n]},{3},3]

OpenersExampleSubsubsection1(Spacer1)Higher-Dimensional List Substitution Systems  (5)

SubstitutionSystem[{0->{{0,0},{0,0}},1->{{1,0},{1,1}}},{{1}},2]

ArrayPlot/@SubstitutionSystem[{0->{{0,0},{0,0}},1->{{1,0},{1,1}}},{{1}},3]

Arrays do not have to be square:

ArrayPlot/@SubstitutionSystem[{0->{{0,0,0},{0,0,0}},1->{{1,0,0},{1,1,1}}},{{1}},3]

Arrays can have any depth:

Image3D/@SubstitutionSystem[{0->{{{0,0},{0,0}},{{0,0},{0,0}}},1->{{{1,0},{0,0}},{{1,1},{1,1}}}},{{{1}}},3]

The right-hand side of a rule can be a (RefLink[SparseArray, paclet:ref/SparseArray]):

ArrayPlot/@SubstitutionSystem[{0->SparseArray[{{2,2}->1}],1->SparseArray[{{1,1}->1,{2,2}->1}]},{{1}},5]

(RefLink[SparseArray, paclet:ref/SparseArray]) as an initial condition:

SubstitutionSystem[{0->{{0,1},{1,0}},1->{{0,0},{0,0}}},SparseArray[{{1,1}->1}],2]

OpenersExampleSubsubsection2(Spacer1)String Substitution Systems  (2)

A string substitution system:

SubstitutionSystem[{"A"->"AB","B"->"BA"},"A",5]

Use any characters in the strings:

SubstitutionSystem[{"a"->"aA","A"->"Aa"},"A",5]

SubstitutionSystem[{"α"->"αβ","β"->"βα"},"β",5]

SubstitutionSystem[{"○"->"○■","■"->"■○"},"■",5]

Arrange output in a column:

Column[%]

Characters that do not appear in the rules are not replaced at each step:

SubstitutionSystem[{"A"->"AB","B"->"BA"},"AC",5]

Include additional characters in rules:

SubstitutionSystem[{"A"->"ABx","B"->"BA"},"A",5]

OpenersExampleSubsubsection3(Spacer1)Time Step Specifications  (6)

Steps 0 through 5:

SubstitutionSystem[{"A"->"AB","B"->"A"},"A",5]

Step 5 only:

SubstitutionSystem[{"A"->"AB","B"->"A"},"A",{5}]

Steps 3 through 5:

SubstitutionSystem[{"A"->"AB","B"->"A"},"A",{3,5}]

Odd-numbered steps:

SubstitutionSystem[{"A"->"AB","B"->"A"},"A",{1,5,2}]

Apply a single step of evolution:

SubstitutionSystem[{"A"->"AB","B"->"A"},"ABBAABAB"]

Apply in operator form:

NestList[SubstitutionSystem[{"A"->"AB","B"->"A"}],"ABAA",5]

OpenersExampleSection2(Spacer1)Generalizations & Extensions  (1)

Set up neighbor-dependent string rules; rules are applied in the order given:

SubstitutionSystem[{"AA"->"AB","B"->"BA","A"->"B"},"AAA",7]

OpenersExampleSection4(Spacer1)Applications  (3)

Steps in constructing a Cantor set:

ArrayPlot[{#}]&/@SubstitutionSystem[{1->{1,0,1},0->{0,0,0}},{1},3]

Create an analogous 2D nested object:

ArrayPlot/@SubstitutionSystem[{1->{{1,1,1},{1,0,1},{1,1,1}},0->ConstantArray[0,{3,3}]},{{1}},5]

3D Menger sponge:

Image3D/@SubstitutionSystem[{1->1-CrossMatrix[{1,1,1}],0->ConstantArray[0,{3,3,3}]},{{{1}}},3]

Generate a "C curve" fractal:

Graphics[Line[AnglePath[(-1)^# Pi/2]]]&/@SubstitutionSystem[{0->{0,0,1},1->{1}},{0},{4,10}]

OpenersExampleSection5(Spacer1)Properties & Relations  (2)

Approximate a Cantor staircase function:

ListLinePlot[Accumulate[#]]&/@SubstitutionSystem[{1->{1,0,1},0->{0,0,0}},{1},{2,5}]

Plot[CantorStaircase[x],{x,0,1}]

Generate steps in a Thue–Morse substitution system:

SubstitutionSystem[{0->{0,1},1->{1,0}} ,{0},5]

The output at each step k is given by (RefLink[ThueMorse, paclet:ref/ThueMorse])[(RefLink[Range, paclet:ref/Range])[0,2^k-1]:

Last[%]==ThueMorse[Range[0,2^5-1]]

OpenersExampleSection6(Spacer1)Neat Examples  (1)

SubstitutionSystem[{"☺"->"🐺☺","🐺"->"☺"},"🐺",8]//Column

3D substitution system based on the Levi–Civita tensor:

Image3D/@SubstitutionSystem[{1->Abs[LeviCivitaTensor[3]],0->ConstantArray[0,{3,3,3}]},{{{1}}},3]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[RulePlot, paclet:ref/RulePlot])  ▪  (RefLink[NestList, paclet:ref/NestList])  ▪  (RefLink[Replace, paclet:ref/Replace])  ▪  (RefLink[StringReplace, paclet:ref/StringReplace])  ▪  (RefLink[Flatten, paclet:ref/Flatten])  ▪  (RefLink[ArrayFlatten, paclet:ref/ArrayFlatten])  ▪  (RefLink[ThueMorse, paclet:ref/ThueMorse])  ▪  (RefLink[RudinShapiro, paclet:ref/RudinShapiro])  ▪  (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton])  ▪  (RefLink[AnglePath, paclet:ref/AnglePath])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Iterated Maps & Fractals, paclet:guide/IteratedMapsAndFractals])}, {▪(RefLinkPlain[Computational Systems, paclet:guide/ComputationalSystemsAndDiscovery])}, {▪(RefLinkPlain[Discrete Mathematics, paclet:guide/DiscreteMathematics])}, {▪(RefLinkPlain[Boolean Computation, paclet:guide/BooleanComputation])}})}})