Determining the size of an L-System string

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Post Reply
drwhat
Posts: 41
Joined: Tue Sep 06, 2011 3:56 am

Determining the size of an L-System string

Post by drwhat » Sat Jul 02, 2016 1:04 pm

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.

v6ph1
Posts: 113
Joined: Mon Aug 25, 2014 6:14 pm

Re: Determining the size of an L-System string

Post by v6ph1 » Sat Jul 02, 2016 1:40 pm

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)
Image

Post Reply