Page 1 of 1

Determining the size of an L-System string

Posted: Sat Jul 02, 2016 1:04 pm
by drwhat
I've been writing a program to play around with L-Systems (Lindenmayer System). https://en.wikipedia.org/wiki/L-system if your curious about them. I'd like to add a progress bar for higher order calculation, but to do that I need to develop a method to determining the total number of items that will be in the final string. I was wondering if there is an easy way to determine the total number of items in the final string (if not necessarily what they are). For example if you had this sytem.
A->AB
B->A
Iniital String = A
Starting with A you get :
A = 1
AB = 2
ABA = 3
ABAAB = 5
ABAABABA = 8
This just continues on with the Fibonacci sequence.
Another example is the Dragon Curve (which includes some constants).
X = X+YF+
Y=−FX−Y
Initial String = FX
FX = 2
FX+YF+ = 6
FX+YF++−FX−YF+=14

and grows rather quickly. I'd like to be able to figure out a method to determine the total string length of a paticular order.

Re: Determining the size of an L-System string

Posted: Sat Jul 02, 2016 1:40 pm
by v6ph1
Like the Fibonacci series can be calculated by a matrix multiplication, the length of these strings can be calculated with matrix multiplication as well:

each Symbol has a row and col in this matrix.

e.g. 1:
A-> AB
B-> A
is transformed to
_ A B
A 1 1
B 1 0
Then use left multiplication with the start string (1,0) and a right multiplication with the counting function (1,1).

The second form can be translated to:
_ X Y F + -
X 1 1 1 2 0
Y 1 1 1 0 2
F 0 0 1 0 0
+ 0 0 0 1 0
- 0 0 0 0 1

start string is (1,0,1,0,0) and the counting function is (1,1,1,1,1)