[canjobear]

> No concept of recursive "generations" in phrase structure grammars!

Not sure what you're getting at here. Generation in a CFG proceeds recursively until no more terminals can be rewritten. If "f" is a nonterminal then you'd keep rewriting just as in an L-system and you'd generate the strings you want just fine. Or is what is distinctive the fact that you can limit the number of "generations"? It seems you could simulate this in a CFG too.

[YeGoblynQueenne]

Yes, that's what I mean by "recursive generations". L-System strings are interpreted in successive generations where the output of generation n becomes the input of generation n+1. The recursion I refer to here is at the level of generation steps.

You can simulate this with a parser for e.g. CFGs like you say, but then you need an outer loop that feeds the parsed strings back to the parser.

There's also a subtlety that I omitted in my earlier comment- apologies! but it's really a bit subtle. In L-Systems, strings are made up of "variables" and "constants", which are closely related to nonterminals and terminals, but are not exactly the same: in phrase-structure grammars, non-terminal symbols cannot appear in strings, only in grammar rules.

So for instance, the Dragon Curve rule I give above, "f -> f+g", means "wherever 'f' appears in a string, replace it with 'f+g'". To get the same result in a phrase-structure grammar you need to further define "f" as a pre-terminal, expanding to a single "f" character.

So for a CFG-parser-with-an-outer-loop to work on an L-System one would also need to modify the L-System to be a full CFG. To make it clear, here's the definition of the Dragon Curve L-System, from my example above:

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

And here is its redefinition as a CFG, with nonterminals capitalised:

  F -> F+G
  G -> F-G
  F -> f
  G -> g

I think it's easier to see that these are different objects. I bet we'd find that, for every L-System, there's a phrase-structure grammar that accepts the same strings (but not necessarily generates the same strings only) and that is a simple re-write of the L-System with variables replaced by pre-terminals, as I do above, kind of like a standard form (not normal; because not fully equivalent). That may even be something well-known by L-Systems folks, I don't know.

Btw, the Dragon Curve L-system is described as an OL-System, that matches a Regular language. The grammar above is context-free but that's OK, a CFG can parse strings of a Regular language. I believe L-System languages go up to context-free expressivity, but I'm not sure, there are also parameterised L-Systems that may go beyond that.

[canjobear]

Interesting. What I was thinking was you could get the bounded-number-of-generations behavior by defining nonterminals with indices. Like this CFG which would rewrite for K steps.

S -> F_K

F_i -> F_{i-1} + G_{i-1} for i>0

G_i -> F_{i-1} - G_{i-1} for i>0

F_0 -> f

G_0 -> g

This kind of CFG is used for example by https://journals.aps.org/prx/pdf/10.1103/PhysRevX.14.031001