L-Systems

Lindenmayer Systems, ou L-Systems, são uma linguagem formal criada em 1968 pelo biólogo húngaro Aristid Lindenmayer [1], com o objetivo de estudar e modelar diversos fenômenos de desenvolvimento biológico: crescimento de plantas, reprodução de bactérias, organismos multicelulares, etc.

Um L-System é composto por três elementos: um alfabeto de símbolos; um axioma; e um conjunto de regras (ou produções).

O funcionamento de um L-System consiste na substituição recursiva de padrões em uma cadeia de módulos. Um organismo é representado por uma cadeia de módulos, onde cada módulo é uma instância de um símbolo do alfabeto, e pode ou não conter parâmetros numéricos. Partindo do axioma, a cadeia de módulos inicial, as regras indicam como cada módulo deve ou não ser substituido a cada iteração do sistema, gerando então uma nova cadeia. A sintaxe de uma regra é:


contexto à esquerda     <     antecessor     >     contexto à direita     :     condição     -->     sucessor


A cada geração, para cada ocorrência de <antecessor> na cadeia, o sistema avalia a expressão <condição> e, se o resultado for "verdadeiro", então <antecessor> é substituido por <sucessor>. Pode não haver uma <condição> em algumas regras; nesse caso, considera-se que <condição> é sempre verdadeira (a substituição sempre é feita). A ordem em que as regras são dadas no sistema é importante: caso mais de uma regra possa ser aplicada a um mesmo módulo, aplica-se a que aparecer primeiro na lista de regras.

Uma regra pode ser sensível a contexto, o que significa que a substituição depende não apenas de cada módulo, mas também dos módulos adjacentes a ele na cadeia de módulos. Nesses casos, para que a substituição ocorra é necessário que o módulo que vem antes do módulo a ser substituído seja igual a <contexto à esquerda>, e que o módulo que vem depois seja igual a <contexto à direita>. Uma regra não precisa ser obrigatoriamente sensível a contexto, e também não precisa ser sensível a ambos os contextos simultaneamente.

Por exemplo, o seguinte L-System foi proposto por Lindenmayer para simular algas que se reproduzem assexuadamente, onde o caractere A representa uma alga adulta, e o caractere B representa uma alga recém-nascida:

alfabeto: { A B }

axioma:    B

regras:
    A --> AB
    B --> A

Neste exemplo, a primeira regra simboliza uma alga adulta se reproduzindo, enquanto a segunda regra simboliza o crescimento de uma nova alga. Não há condições a serem satisfeitas, ou seja, as substituições sempre ocorrem. Este L-System produz a seguinte seqüência de cadeias:

n0 (axioma): B
n1: A
n2: AB
n3: ABA
n4: ABAAB
n5: ABAABABA
n6: ABAABABAABAAB
n7: ABAABABAABAABABAABABA

É curioso notar que, neste exemplo, os tamanhos das cadeias formam a série de Fibonacci (1 1 2 3 5 8 13 21 ... ), geralmente associada ao crescimento de populações.