Tipos de L-systems

O processo global para o sistema Fibonacci funciona proque este L-system é livre de contexto significando que cada regra de produção toma conta apenas de um único símbolo, e não se importando quem seus vizinhos sejam. É possível considerar L-systems sensíveis ao contexto onde as regras de produção aplicam-se a um símbolo particular somente se o símbolo tem certos vizinhos. Aqui está um exemplo:

Ele descreve uma população com uma dinâmica elaborada. Se um a não tem nada a direita (isto é o que a notação  significa), ele matura um b (se tranasforma ). Se ele tem um adulto b a direita, o adulto o "mata"  e ele desaparece. Se um adulto b tem uma criança a no lado direito, ele fica "velho" e se torna um c. Pela produção  , se dois b's ocorrem consecutivamente, eles reproduzem-se e produzem um a entre eles. Um organismo velho c morre depois de uma geração. Em todos os outros casos os símbolos ficam os mesmos. A evolução deste L-system é o seguinte:

Table 3: Crescimento e declíneo da População.

Após este ponto as gerações são imutáveis.

Nós ainda não estipulamos que para cada símbolo no alfabeto haja exatamente uma produção, apesar de isto ser verdade para nossos primeiros exemplos. Se há de fato exatamente uma produção para cada símbolo, então o L-system é chamado de determinístico e a seqüência de gerações   é unicamente definida como uma seqüência de elementos de . Se houver mais do que uma produção para um símbolo dado, digamos   e  , nós precisaríamos de um critério para decidir quando aplicar cada regra. Uma possibilidade é usar uma das possíveis produções com certas probabilidades. Nesta seção, nós consideraremos apenas L-systems determinísticos. A classe mais simples de L-systems, determinístico livre de contexto, é popularmente chamada de D0L-system (D0L vem de determinístico e 0-contexto ou livre de contexto). Para fornecer um entendimento intuitivo da principal idéia por traz dos D0L-systems , vamos considerar este exemplo dado por  Prusinkiewicz e Lindenmayer (1991) (ver figura mais abaixo).

Considere strings constituídos de duas letras a e b (eles podem ocorrer muitas vezes em um string). Para cada letra nós especificamos uma regra de substituição. A regra a -> ab significa que a letra a deve ser substituída pelo string ab, e a regra b -> a que a letra b deve ser substituída por um a. O processo começa a partir de um string distinto chamado axioma. Vamos assumir que ele consiste de uma letra simples b. No primeiro passo de derivação (o primeiro paso da substituição) o axioma b é trocado atraves da produção b -> a. No segundo passo a é substituido por ab usando a produção a -> ab. A palavra ab consiste de duas letras, ambas são simultaneamente trocadas no próximo passo de derivação. Então , a é substituído por ab , b é substituído por a, e o string resultante será aba . Da mesma maneira (por trocas simultâneas de todas as letras), o string aba gera abaab que por sua vez gera abaababa, depois abaababaabaab, e assim por diante.

      b
      |
      a
      _|_
       a     b
      _|        \
      a   b        a
      _|    |          |_
       a    b  a        a   b
    _/       |   |_      |_   \
     a  b     a  a  b   a  b  a

Definições formais de D0L-systems e suas operações podem ser encontradas em (Prusinkiewicz and Hanan 1989; Prusinkiewicz and Lindenmayer 1991).

O estudo das gerações de subconjuntos formais de  são originarios da teoria das linguagens formais, advinda de Chomsky como uma forma matemática para discutir a formação e evolução de linguagens naturais. Por essa razão, qualquer subconjunto S de  é chamado uma linguagem. Linguagens L-systems são exemplos de a much broader class conhecida em teoria da ciência da computação como linguagens recursivamente enumeraveis. Alguns aspectos ou características novas de L-systems são a natureza paralela da evolução de uma palavra para a próxima e a natureza dinâmica da linguagem que nós podemos imaginar como o crescimento sobre tempo.

O processo global de Fibonacci poderia ser considerado um simples exemplo do que é conhecido como comportamento emergente na teoria dos sistemas dinâmicos, comportamento que é evidente no desenvolvimento do sistema. Nós veremos este tipo de fenômeno várias vezes no curso. Este processo em particular é uma cadeia ou lei de concatenação, em que as muitas gerações passadas are encadeadas para formar a próxima geração. Em geral, nós dizemos que o L-system satisfaz uma lei de cadeia se existe uma seqüência de inteiros  tal que