Generating a pattern from user-defined rules

Question

I want to generate a list of $L$ and $S$ according to the following rule:
upon each iteration, replace

• $S \rightarrow L$
• $L \rightarrow LS$

Such that, starting with $L$:

$ L \rightarrow LS \rightarrow LSL \rightarrow LSLLS \rightarrow LSLLSLSL \rightarrow LSLLSLSLLSLLS \rightarrow \dots$

How can I automate this with Mathematica? I just want to specify the starting letter and the number of iteration and I'd want it to spit out the final result.

Answer 1

For the 5th iterate:

Nest[
 Replace[#, {L -> Sequence[L, S], S -> Sequence[L]}, {1}] &,
 {L},
 5
 ]

{L, S, L, L, S, L, S, L, L, S, L, L, S}

And for the list of first 5 iterates:

NestList[
 Replace[#, {L -> Sequence[L, S], S -> Sequence[L]}, {1}] &,
 {L},
 5
 ]

{{L}, {L, S}, {L, S, L}, {L, S, L, L, S}, {L, S, L, L, S, L, S, L}, {L, S, L, L, S, L, S, L, L, S, L, L, S}}

Edit:

SubstitutionSystem operates on strings instead. It is a bit faster because it is specifically designed for Lindenmayer systems:

L = "L";
S = "S";
a = StringJoin /@ NestList[
      Replace[#, {L -> Sequence[L, S], S -> Sequence[L]}, {1}] &,
      {L},
      20
      ]; // AbsoluteTiming // First
b = SubstitutionSystem[{"L" -> "LS", "S" -> "L"}, "L", 20]; // AbsoluteTiming // First

a == b

0.004506

0.001265

True

PS.: As Carl Woll pointed out, the following will return only the 20th iterate.

c = SubstitutionSystem[{"L" -> "LS", "S" -> "L"}, "L", {20}];

Answer 2

You may use ReplaceRepeatedwith its MaxIterationsoption.

ReplaceRepeated[{L}, {L -> Sequence[L, S], S -> Sequence[L]}, 
 MaxIterations -> 5]

{L, S, L, L, S, L, S, L, L, S, L, L, S}

Hope this helps.

Answer 3

A recursive method:

ClearAll[f]
f[L] = Sequence[L, S];
f[S] = L;
f[a__, b_] := f[a, b] = Sequence[f @ a, f @ b]

List @ Nest[f, L, 7]

{L, S, L, L, S, L, S, L, L, S, L, L, S, L, S, L, L, S, L, S, L, L, S, L, L, S, L, S, L, L, S, L, L, S}