Introdução aos L-systems

Sistemas Lindenmayer, mais conhecidos por L-Systems, são um formalismo matemático proposto pelo biológo Aristid Lindenmayer em 1968 como um fundamento para a teoria axiomática do desenvolvimento ou crescimento biológico. L-systems são um tipo particular de sistema simbólico dinâmico que dá uma interpretação geométrica para a evolução dos sistemas. Mais recentemente, L-systems tem tido muitas aplicações em computação gráfica (Smith 1984, Prusinkiewicz e Hanan 1989; Prusinkiewicz and Lindenmayer 1991). Duas das principais áreas incluem geração de fractais e modelamento realístico das plantas.

Um L-system é um autômato para modelar o desenvolvimento célular. Células são representadas por símbolos e a subdivisão é modelada pela troca desses símbolos por strings de símbolos. Aqui está um exemplo simples de L-system com dois tipos de células representadas pelas letras A e B. A célula A se subdivide em duas células representadas pela string AB. A célula B se subdivide em duas células representadas pela string BA. A ordem dos símbolos é relevante em L-systems. O organismo abstrato modelado por este L-system cresce pela repetição de subdivisões das células. No nascimento o organismo é uma única célula A. Depois de uma subdivisão o organismo tem duas células representadas pela string AB. Depois de duas subdivisões, cada célula subdividi-se de acordo com as regras de subdivisão acima, o organismo tem quatro células dadas pela string ABBA. Depois de três subdivisões o organismo é representado pela string ABBABAAB e depois de quatro subdivisões o organismo tem 16 células representadas pela string ABBABAABBAABABBA.

A linguagem utilizada para gerar L-systems é axiomatizada em caracteres, promovendo uma conecção entre o problema lógico e a solução visual. Ela usa a reescrita de símbolos como técnica básica, criando assim objetos complexos pela interação de um conjunto de regras ou produções para substituir partes de uma geometria inicial simples. A geometria inicial é chamada de inicializador (ou axioma) e as regras que dão instruções de substituições são chamadas de geradores ou produções.

A idéia central  para L-systems é a noção de reescrita (substituição ), onde o objetivo básico é definir objetos complexos por sucessivas substituições de partes simples do objeto usando um conjunto de regras ou produções de reescrita. Uma reescrita pode ser passada recursivamente.

Os sistemas de reescrita mais estudados e entendidos operam em strings de caracter. O trabalho de Chomsky em linguagens formais(1957) gerou um grande interesse em sistemas de reescrita. Subsequentemente, surgiu um período de fascinação com sintaxe, gramáticas e suas aplicações em ciência da computação, dando início ao campo de linguagens formais.

O trabalho de Aristid Lindenmayer introduziu um novo tipo de mecanismo de reescrita de strings chamado L-systems. A diferença essencial entre as gramáticas de Chomsky e L-systems se dá no método de aplicação das produções. Nas gramáticas de Chomsky as produções são aplicadas sequencialmente, enquanto que nos L-systems elas são aplicados em paralelo, substituindo-se simultaneamente todas as letras de uma dada palavra. Esta diferença reflete a motivação biológica dos L-systems. As produções pretendem simular as divisões celulares em organismos multicelulares, em que muitas divisões podem ocorrer ao mesmo tempo.

Os L-systems tem a propriedade única de gerar as produções em paralelo. Isto significa que qualquer problema que  dependa de permutações para sua solução pode ser calculado simultaneamente ao invés de sequencialmente. Por exemplo, tomando-se uma linha reta e dividindo-a em duas, dobra o número de segmentos. Sucessivos subdivisões redobram o número de segmentos. Uma descrição mais completa desta analogia geometrica será dada nas sessões seguintes.

Por usar uma geometria simples para ilustrar resultados paralelos, tornou-se possível olhar para todos valores produzidos por uma equação. Consequentemente, L-systems tornam-se um ferramenta útil para avaliar resultados num relance e observar padrões surgidos no estudo de um dado problema.