Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am working the a subject guide on involving $L$-Systems and have the alphabet $A = \{a, b, c\}$. The initiator is the string $a$ and the rules of substitution $a \to ba$, $b \to ccb$, $c \to a$.

The study guide gives the first five generations as:

$$[a] \to [ba] \to [ccba] \to [acba] \to [aaba] \to [aaccba]$$

I can't for the life of me figure out how this works. No rules regarding the order of substitution are provided, and my lecturer say's that it is possible to get to this.

Does anybody have any ideas?

share|cite|improve this question
    
Generally, all of the substitutions are assumed to occur simultaneously. The thing is, the chain of generations you've given doesn't seem to follow the rule (for example, [ba] should go to [ccbba]). Are you sure you copied down the information from the study guide correctly? – Will Dana Feb 23 '12 at 16:42
    
I am afraid so. Checked and double-checked. – Ray Feb 23 '12 at 17:45
up vote 1 down vote accepted

It looks like only one symbol is substituted in one step. The symbol $c$ gets highest priority, followed by $b$ and then $a$. When there are multiple instances of the same symbol, the leftmost is changed. But of course this is guessing, and the example is too short to allow much confidence.

share|cite|improve this answer
    
I agree with this nukka. – Hautdesert Feb 26 '12 at 3:31

Lindenmayer systems make all substitutions at once; this is one of their defining features. This is mentioned in the book The Algorithmic Beauty of Plants on page 3 of chapter 1, "In Chomsky grammars productions are applied sequentially, whereas in L-systems they are applied in parallel and simultaneously replace all letters in a given word." This book is one of the go to references for L-Systems (other than Lindenmayer's original papers in computational biology).

There is no order of precedence in the substitution. The sequence should be

a -> ba -> ccbba -> aaccbba -> babaaaccbccb -> ccbbaccbbababaaaccbaaccb ->....

if the rules

a -> ba b -> ccb c -> a are applied all at once at each step, as they should be for all L-Systems.

I'm gonna write the evolution again blocked out so that each substitution is in brackets.

a -> [a] -> [ba] -> ba -> [b][a] -> [ccb][ba] -> ccbba -> [c][c][b][b][a]

-> [a][a][ccb][ccb][ba] -> aaccbccbba -> etc.

are applied. Please inform your instructor or T.A. that they have made a serious error in their study guide. Such an error could dissuade students from learning the material - especially introverted students or underrepresented students such as women and minorities. The student might think that the error is in their understanding or even capacity to understand rather than with the educator's carelessness. Out of curiosity how did this topic come up/what type of class?

(there is a small chance that your professor may have been referring to second order or even contextual L-systems which are more complex, but if s/he were referring to that they would have listed more axioms).

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.