{"id":479,"date":"2007-07-30T21:30:37","date_gmt":"2007-07-30T21:30:37","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/07\/30\/l-system-fractals\/"},"modified":"2018-11-27T20:27:47","modified_gmt":"2018-11-28T01:27:47","slug":"l-system-fractals","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/07\/30\/l-system-fractals\/","title":{"rendered":"L-System Fractals"},"content":{"rendered":"

\"fb.gif\"<\/p>\n

In the post about Koch curves, I talked about how a grammar-rewrite system could be used to describe fractals. There’s a bit more to the grammar idea that I originally suggested. There’s something called an L-system (short for Lindenmayer system<\/em>, after Aristid Lindenmayer, who invented it for describing the growth patterns of plants), which is a variant of the Thue grammar, which is extremely useful for generating a wide range of interesting fractals for describing plant growth, turbulence patterns, and lots of other things.<\/p>\n

<\/p>\n

The main difference between an L-system and a simple grammar rewrite system is that in a simple rewrite system, in each step, you replace an occurence (or sometimes all occurences) of one<\/em> symbol – the left-hand side of the grammar rule – with the contents of the right-hand side of the grammar rule. In an L-system, in each step, you replace all<\/em> instances of all<\/em> symbols that match any rule as a single atomic step.<\/em><\/p>\n

Both simple rewrite systems and L-systems take the same inputs – a grammar, but the behave differently. If you think of them as computation systems, L-systems have a kind of parallelism to them. Let’s look at how they’re made up, and then I’ll show you an example of how different their results can be.<\/p>\n

The grammar of L-systems and simple rewrite systems consist of:<\/p>\n

    \n
  1. A set S of symbols, called non-terminal symbols<\/em><\/li>\n
  2. A set T of symbols, called non-terminal symbols<\/em><\/li>\n
  3. A set R of rewrite-rules<\/em> that map from a symbol l\\in S to a sequence of symbols from \\text{rhs} \\in (S\\cup T)^*. Each rule in R says that the non-terminal symbol l can be replaced by the sequence of symbols in rhs.<\/li>\n
  4. A special distinguished symbol in S called the initiator<\/em>. Every use of the rewrite system will start with a single instance of the initiator.<\/li>\n<\/ol>\n

    To demonstrate the difference, let’s look at a simple grammar, and its evolution as an L-system compared to a simple rewrite system. The non-terminal symbols consist of {A,B}; the terminal symbols set will be empty; and the initiator will be “A”.<\/em><\/p>\n

      \n
    • A → AB<\/li>\n
    • B → A<\/li>\n<\/ul>\n

      Here’s a sequence of steps from the simple rewrite and the L-system:<\/p>\n\n\n\n\n\n\n\n
      Simple rewrite<\/th>\nL-system<\/th>\n<\/tr>\n
      AB<\/td>\nAB<\/td>\n<\/tr>\n
      AA<\/td>\nABA<\/td>\n<\/tr>\n
      ABAB<\/td>\n ABAAB<\/td>\n<\/tr>\n
      AAAA<\/td>\nABAABABA<\/td>\n<\/tr>\n
      ABABABAB<\/td>\nABAABABAABAAB<\/td>\n<\/tr>\n<\/table>\n

      The parallelism of the L-system is very useful in defining fractals; it’s part of the key to why some fractals can be described so easily and naturally using L-systems: the self-similarity of the fractal in different positions corresponds to the parallel expansions. For example, here’s a version of Cantor’s dust as an L-system:<\/p>\n

        \n
      1. Non-terminals: {B,W}; terminals={}<\/li>\n
      2. Rules: B→BWB, W→WWW<\/li>\n
      3. Initiator: B<\/li>\n<\/ol>\n

        A series of steps of this are: “B”, “BWB”, “BWBWWWBWB”, “BWBWWWBWBWWWWWWWWWBWBWWWBWB”. If you think of “B” as “black point”, and “W” as “white point”, then you can easily see that the limit of this L-system is a drawing of the Cantor dust. And you can also see how the parallelism of the L-system makes it work so easily. Without it, you’d need to do something like horizontal passes across the string; and to do that, you would need to add some kind of place-holder into the rules to keep track of which symbols had been modified by a given pass. The L-system makes it much easier.<\/p>\n

        A neater example of how we can do fractals using L-systems is a tracing of the Sierpinski gasket. This is very typical of how we do fractal curves with L-systems: the grammar generates a set of instructions for a pen or turtle. (There are other tricks for how to use L-systems for higher dimension structures, but for this post, we’ll stick with curves.<\/p>\n

        To trace the gasket, we’ll use a set of symbols with meanings for turtle drawings:<\/p>\n

          \n
        • “+” is a terminal symbol which means “turn right 60 degrees”.<\/li>\n
        • “-” is a terminal symbol which means “turn left 60 degrees”.<\/li>\n
        • “1” and “2” are both non-terminal<\/em> symbols which mean “go forward”. We use the two different symbols for “forward” because there are two different kinds of expansions, which should
          \nalternate.\n<\/li>\n<\/ul>\n

          \"sier-trace.png\"<\/p>\n

            \n
          1. Rules:\n
              \n
            • 1 → 2-1-2<\/li>\n
            • 2 → 1+2+1<\/li>\n<\/ul>\n
            • Initiator: 1<\/li>\n<\/ol>\n

              Over to the right is the sierpinski tracing after 6 iterations.<\/p>\n

              One of the more famous self-intersecting fractal curves, the dragon curve, is very natural as an L-system; it involves one more trick beyond what we’ve done so far – the instruction string is going to include no-ops to drive the expansions; all of the instructions are terminal symbols; non-terminals are interspersed, and do the actual work of generating the fractal structure.<\/p>\n

              \"dragon.png\"<\/p>\n

                \n
              1. Terminals:\n
                  \n
                • +: right 90 degrees<\/li>\n
                • -: left 90 degrees<\/li>\n<\/ul>\n
                • Rules:\n
                    \n
                  • 1 → 1+2f+<\/li>\n
                  • 2 → -f1-2<\/li>\n<\/ul>\n
                  • Initiator: “f1”<\/li>\n<\/ol>\n

                    Over to the right is the dragon after 8 iterations.<\/p>\n

                    One last one for today – it’s quite hairy for a planar L-system, but it’s a good one! I came across this on Wikipedia; I haven’t seen it elsewhere described via an L-system. It’s a fractal fern – a pattern that comes out looking like a sprig of dill or a frond of fennel. The complexity of it comes from the way it handles the branches in the fronds: in addition to the use of non-terminals as expansion drivers, it also uses a stack. The stack marks a position and direction that the turtle was facing at a particular point in time. There’s a terminal symbol that indicates that the current position\/heading should be pushed onto the stack, and a terminal that indicates that the stack should be popped, and the turtle set to the position heading in the popped value.<\/p>\n

                      \n
                    1. Terminals:\n
                        \n
                      • Fwd<\/b>: move forwards drawing a line.<\/li>\n
                      • Right<\/b>: rotate right 25 degrees.<\/li>\n
                      • Left<\/b>: rotate left 25 degrees.<\/li>\n
                      • [<\/b>: push turtle position\/heading.<\/li>\n
                      • ]<\/b>: pop turtle position\/heading.<\/li>\n<\/ul>\n<\/li>\n
                      • Non-terminals:\n
                          \n
                        • X<\/b><\/li>\n<\/ul>\n<\/li>\n
                        • Rules:\n
                            \n
                          • X → Fwd,Left[[X]Right,X]Right,Fwd[Right,Fwd,X]Left,X <\/li>\n
                          • Fwd → Fwd,Fwd<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

                            And here’s the result of running it for 6 iterations:<\/p>\n

                            \"fern.png\"<\/p>\n","protected":false},"excerpt":{"rendered":"

                            In the post about Koch curves, I talked about how a grammar-rewrite system could be used to describe fractals. There’s a bit more to the grammar idea that I originally suggested. There’s something called an L-system (short for Lindenmayer system, after Aristid Lindenmayer, who invented it for describing the growth patterns of plants), which is […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[86],"tags":[152,159,189],"class_list":["post-479","post","type-post","status-publish","format-standard","hentry","category-fractals","tag-fern","tag-fractal","tag-l-system"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7J","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/479","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=479"}],"version-history":[{"count":2,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/479\/revisions"}],"predecessor-version":[{"id":3672,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/479\/revisions\/3672"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=479"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=479"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=479"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}