Lindenmayer.jl: Defining recursive patterns in Julia

L-Systems are not phrase-structure grammars. Some are similar to Regular, others to Context-Free grammars, but they're a different grammar formalism.

The difference is that L-system rules are all applied simultaneously and consume an entire string before repeating the process in steps called "generations", where each generation takes as input the output of the previous one. Generations continue indefinitely, generating ever-longer strings, up to a limit set by the user.

For instance, take the Dragon Curve L-System,

  Axiom: f
  Constants: +,-
  f -> f+g
  g -> f-g

Suppose we wanted to execute two generations of this L-System. Starting with the axiom, "f", the first generation replaces "f" with "f+g". The next generation operates on this new string. The "f" in "f+g" is replaced with "f+g", the "+" stays the same because it's a constant and the "g" is replaced with "f-g". This creates the string f+g+f-g. And so on.

If the same L-System was given as a phrase-structure grammar, given the axiom, "f", as input, the "f" would be expanded to f+g, and the process would stop there. No concept of recursive "generations" in phrase structure grammars! If we wanted to generate the string "f+g+f-g" with a phrase structure grammar we'd need to give the input "f+g", i.e. the L-System output of the first generation.

More to the point, the execution of L-Systems in successive generations limits the strings that can be generated by a set of rules, if we take those rules as an L-System grammar. For example, the Dragon Curve Rules above, interpreted as an L-System can only generate the strings:

  f --> f+g
  f+g --> f+g+f-g
  f+g+f-g --> f+g+f-g+f+g-f-g

Where the strings before the "-->" are inputs and the ones after, outputs, and each string is the output of one generation.

Whereas the same rules, interpreted as a Regular, phrase-structure, grammar, accept all the following one- to three-character strings :

  + --> +
  - --> -
  ++ --> ++
  +- --> +-
  -+ --> -+
  -- --> --
  +++ --> +++
  ++- --> ++-
  +-+ --> +-+
  +-- --> +--
  -++ --> -++
  -+- --> -+-
  --+ --> --+
  --- --> ---
  f --> f+g
  g --> f-g

And so on up to 229 strings of one to six characters (as in the input of the third-generation Dragon Curve above).

But none of those strings, other than the penultimate one, are correct Dragon Curve strings, meaning that they can't be interpreted so as to draw a Dragon Curve fractal, e.g. with a Turtle interpreter as in the article above.

To be fair to your comment, the first time I read the claim that L-Systems are different in that way I scoffed and wrote it off as an attempt to justify an unnecessary new notation. I put the insistence on a new notation down to vanity and forgot about it.

I only realised that L-Systems are really a different grammar formalism when I tried to implement a simple L-System as a Regular grammar, in Prolog's Definite Clause Grammars (DCG) notation. DCGs are syntactic sugar for ordinary Prolog definite clauses so a "grammar" in DCG notation is at the same time a L/R parser, that can also be executed as a generator without any changes, a nifty trick that is well suited to the role of L-Systems as generators, rather than recognisers. I won't bore you with the details, but suffice it to say that this natural style of parsing simply doesn't work with L-System grammars, you need a special interpreter to count the generations and pass the output of one to the next. Not complicated, but the point is that just parsing an L-System string as a phrase-structure grammar string, doesn't give you the same results.

Bottom line: L-Systems aren't just trying to be different; they are. They're not phrase-structure grammars. For real.

P.S. And for our shameless plug today, my paper on learning grammars, both phrase-structure grammars and L-Systems:

https://arxiv.org/abs/2507.16405

[deleted]