Sistema L - L-system

As árvores do sistema L formam modelos realistas de padrões naturais

Um sistema L ou sistema de Lindenmayer é um sistema de reescrita paralelo e um tipo de gramática formal . Um sistema L consiste em um alfabeto de símbolos que podem ser usados ​​para fazer cadeias de caracteres , uma coleção de regras de produção que expandem cada símbolo em uma cadeia maior de símbolos, uma cadeia de " axioma " inicial a partir da qual iniciar a construção e um mecanismo para traduzir as cordas geradas em estruturas geométricas. Os sistemas L foram introduzidos e desenvolvidos em 1968 por Aristid Lindenmayer , um biólogo teórico e botânico húngaro da Universidade de Utrecht . Lindenmayer usou sistemas L para descrever o comportamento das células vegetais e modelar os processos de crescimento do desenvolvimento da planta . Os sistemas L também foram usados ​​para modelar a morfologia de uma variedade de organismos e podem ser usados ​​para gerar fractais auto-semelhantes .

Origens

'Weeds', gerado usando um sistema L em 3D.

Como biólogo, Lindenmayer trabalhou com leveduras e fungos filamentosos e estudou os padrões de crescimento de vários tipos de bactérias , como a cianobactéria Anabaena catenula . Originalmente, os sistemas L foram concebidos para fornecer uma descrição formal do desenvolvimento de tais organismos multicelulares simples e para ilustrar as relações de vizinhança entre as células vegetais. Mais tarde, este sistema foi estendido para descrever plantas superiores e estruturas ramificadas complexas.

Estrutura do sistema L

A natureza recursiva das regras do sistema L leva à auto-similaridade e, portanto, as formas do tipo fractal são fáceis de descrever com um sistema L. Modelos de plantas e formas orgânicas de aparência natural são fáceis de definir, pois ao aumentar o nível de recursão a forma lentamente 'cresce' e se torna mais complexa. Os sistemas Lindenmayer também são populares na geração de vida artificial .

As gramáticas do sistema L são muito semelhantes à gramática semi-Thue (consulte a hierarquia de Chomsky ). Os sistemas L são agora comumente conhecidos como sistemas L paramétricos , definidos como uma tupla

G = ( V , ω, P ),

Onde

  • V (o alfabeto ) é um conjunto de símbolos contendo elementos que podem ser substituídos ( variáveis ) e aqueles que não podem ser substituídos ("constantes" ou "terminais")
  • ω ( início , axioma ou iniciador ) é uma sequência de símbolos de V definindo o estado inicial do sistema
  • P é um conjunto de regras de produção ou produções que definem a maneira como as variáveis ​​podem ser substituídas por combinações de constantes e outras variáveis. Uma produção consiste em duas cordas, a predecessora e a sucessora . Para qualquer símbolo A que seja membro do conjunto V que não apareça no lado esquerdo de uma produção em P, a produção de identidade A → A é assumida; esses símbolos são chamados de constantes ou terminais . (Ver Lei da Identidade ).

As regras da gramática do sistema L são aplicadas iterativamente a partir do estado inicial. São aplicadas tantas regras quanto possível simultaneamente, por iteração. O fato de que cada iteração emprega tantas regras quanto possível diferencia um sistema L de uma linguagem formal gerada por uma gramática formal , que aplica apenas uma regra por iteração. Se as regras de produção fossem aplicadas apenas uma de cada vez, seria simplesmente gerado uma linguagem, em vez de um sistema L. Assim, os sistemas L são subconjuntos estritos de linguagens.

Um sistema L é livre de contexto se cada regra de produção se refere apenas a um símbolo individual e não a seus vizinhos. Sistemas-L livres de contexto são, portanto, especificados por uma gramática livre de contexto . Se uma regra depende não apenas de um único símbolo, mas também de seus vizinhos, ela é denominada sistema-L sensível ao contexto .

Se houver exatamente uma produção para cada símbolo, então o sistema L é considerado determinístico (um sistema L livre de contexto determinístico é popularmente chamado de sistema D0L ). Se houver vários, e cada um for escolhido com uma certa probabilidade durante cada iteração, então é um sistema L estocástico .

O uso de sistemas L para gerar imagens gráficas requer que os símbolos no modelo se refiram a elementos de um desenho na tela do computador. Por exemplo, o programa Fractint usa gráficos de tartaruga (semelhantes aos da linguagem de programação Logo ) para produzir imagens de tela. Ele interpreta cada constante em um modelo do sistema L como um comando de tartaruga.

Exemplos de sistemas L

Exemplo 1: Algas

O sistema L original de Lindenmayer para modelar o crescimento de algas.

variáveis  : AB
constantes  : nenhuma
axioma  : A
regras  : (A → AB), (B → A)

que produz:

n = 0: A
n = 1: AB
n = 2: ABA
n = 3: ABAAB
n = 4: ABAABABA
n = 5: ABAABABAABAAB
n = 6: ABAABABAABAABABAABABA
n = 7: ABAABABAABAABABAABABAABAABABAABAAB

Exemplo 1: Algas, explicado

n=0:               A             start (axiom/initiator)
                  / \
n=1:             A   B           the initial single A spawned into AB by rule (A → AB), rule (B → A) couldn't be applied
                /|     \
n=2:           A B      A        former string AB with all rules applied, A spawned into AB again, former B turned into A
             / | |       | \
n=3:         A B A       A B     note all A's producing a copy of themselves in the first place, then a B, which turns ...
           / | | | \     | \ \
n=4:       A B A A B     A B A   ... into an A one generation later, starting to spawn/repeat/recurse then

O resultado é a sequência de palavras de Fibonacci . Se contarmos o comprimento de cada string, obtemos a famosa sequência de números de Fibonacci (pulando o primeiro 1, devido à nossa escolha do axioma):

1 2 3 5 8 13 21 34 55 89 ...

Se nós gostaríamos de não ignorar o primeiro 1, podemos usar axioma B . Isso colocaria o nó B antes do nó superior ( A ) do gráfico acima.

Para cada string, se contarmos a k -ésima posição da extremidade esquerda da string, o valor será determinado pelo fato de um múltiplo da proporção áurea cair dentro do intervalo . A proporção de A para B da mesma forma converge para a média de ouro.

Este exemplo origina o mesmo resultado (em termos de comprimento de cada fio, não a sequência de uma s e B s) se a regra ( AAB ) é substituído com ( ABA ), excepto que as cadeias são espelhados.

Esta sequência é uma sequência localmente catenative porque , onde é o n geração -ésimo.

Exemplo 2: árvore fractal (binária)

  • variáveis  : 0, 1
  • constantes : “[”, “]”
  • axioma  : 0
  • regras  : (1 → 11), (0 → 1 [0] 0)

A forma é construída alimentando recursivamente o axioma por meio das regras de produção. Cada caractere da string de entrada é verificado em relação à lista de regras para determinar com qual caractere ou string deve ser substituído na string de saída. Neste exemplo, um '1' na string de entrada torna-se '11' na string de saída, enquanto '[' permanece o mesmo. Aplicando isso ao axioma de '0', obtemos:

axioma: 0
1ª recursão: 1 [0] 0
2ª recursão: 11 [1 [0] 0] 1 [0] 0
3ª recursão: 1111 [11 [1 [0] 0] 1 [0] 0] 11 [1 [0] 0] 1 [0] 0

Podemos ver que essa string cresce rapidamente em tamanho e complexidade. Essa string pode ser desenhada como uma imagem usando gráficos de tartaruga , onde cada símbolo é atribuído a uma operação gráfica para a tartaruga realizar. Por exemplo, no exemplo acima, a tartaruga pode receber as seguintes instruções:

  • 0: desenha um segmento de linha terminando em uma folha
  • 1: desenhe um segmento de linha
  • [: empurre a posição e o ângulo, vire à esquerda 45 graus
  • ]: pop posição e ângulo, virar à direita 45 graus

O push e pop referem-se a uma pilha LIFO (a gramática mais técnica teria símbolos separados para "posição push" e "virar à esquerda"). Quando a interpretação da tartaruga encontra um '[', a posição e o ângulo atuais são salvos e são restaurados quando a interpretação encontra um ']'. Se vários valores foram "empurrados", um "pop" restaura os valores salvos mais recentemente. Aplicando as regras gráficas listadas acima à recursão anterior, obtemos:

Exemplo 3: conjunto Cantor

Cantor definido em sete iterations.svg
variáveis  : AB
constantes  : nenhuma
início  : A {seqüência de caracteres inicial}
regras  : (A → ABA), (B → BBB)

Deixe A significar "avançar" e B significar "avançar".

Isso produz o famoso conjunto fractal de Cantor em uma verdadeira linha reta R .

Exemplo 4: curva de Koch

Uma variante da curva de Koch que usa apenas ângulos retos.

variáveis  : F
constantes  : + -
início  : F
regras  : (F → F + F − F − F + F)

Aqui, F significa "puxar para frente", + significa "virar à esquerda 90 °" e - significa "virar à direita 90 °" (veja os gráficos da tartaruga ).

n = 0:
F
Praça Koch - 0 iterações
n = 1:
F + F − F − F + F
Praça Koch - 1 iteração
n = 2:
F + F - F - F + F + F + F - F - F + F - F + F - F - F + F - F + F - F - F + F + F + F - F - F + F
Praça Koch - 2 iterações
n = 3:
F + F − F − F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F + F − F − F + F +
F + F − F − F + F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F + F − F − F + F−
F + F − F − F + F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F + F − F − F + F−
F + F − F − F + F + F + F − F − F + F − F + F − F − F + F − F + F − F − F + F + F + F + F − F − F + F +
F + F - F - F + F + F + F - F - F + F - F + F - F - F + F - F + F - F - F + F + F + F - F - F + F
Praça Koch - 3 iterações

Exemplo 5: triângulo de Sierpinski

O triângulo de Sierpinski desenhado usando um sistema L.

variáveis  : FG
constantes  : + -
início  : F − G − G
regras  : (F → F − G + F + G − F), (G → GG)
ângulo  : 120 °

Aqui, F significa "puxar para frente", G significa "puxar para frente", + significa "virar à esquerda pelo ângulo" e - significa "virar à direita pelo ângulo".

Também é possível aproximar o triângulo de Sierpinski usando um sistema L de curva de ponta de seta de Sierpiński .

variáveis  : AB
constantes  : + -
começo  : A
regras  : (A → B − A − B), (B → A + B + A)
ângulo  : 60 °

Aqui, A e B significam "puxar para frente", + significa "virar à esquerda pelo ângulo" e - significa "virar à direita pelo ângulo" (veja os gráficos da tartaruga ).

Serpinski Lsystem.svg
Evolução para n = 2, n = 4, n = 6, n = 8

Exemplo 6: curva do dragão

A curva do dragão desenhada usando um sistema L.

variáveis  : FG
constantes  : + -
início  : F
regras  : (F → F + G), (G → FG)
ângulo  : 90 °

Aqui, F e G significam "puxar para frente", + significa "virar à esquerda pelo ângulo" e - significa "virar à direita pelo ângulo".

Dragon curve L-system.svg
Curva do dragão para n = 10

Exemplo 7: planta fractal

variáveis  : XF
constantes  : + - []
início  : X
regras  : (X → F + [[X] -X] -F [-FX] + X), (F → FF)
ângulo  : 25 °

Aqui, F significa "puxar para frente", - significa "virar à direita 25 °" e + significa "virar à esquerda 25 °". X não corresponde a nenhuma ação de desenho e é usado para controlar a evolução da curva. O colchete "[" corresponde a salvar os valores atuais de posição e ângulo, que são restaurados quando o "]" correspondente é executado.

Planta fractal para n = 6

Variações

Uma série de elaborações sobre esta técnica básica do sistema L foram desenvolvidas e podem ser usadas em conjunto umas com as outras. Entre elas estão gramáticas estocásticas , gramáticas sensíveis ao contexto e gramáticas paramétricas.

Gramáticas estocásticas

O modelo gramatical que discutimos até agora é determinístico - isto é, dado qualquer símbolo no alfabeto da gramática, existe exatamente uma regra de produção, que é sempre escolhida e sempre executa a mesma conversão. Uma alternativa é especificar mais de uma regra de produção para um símbolo, dando a cada uma delas uma probabilidade de ocorrência. Por exemplo, na gramática do Exemplo 2, poderíamos alterar a regra para reescrever "0" de:

0 → 1 [0] 0

a uma regra probabilística:

0 (0,5) → 1 [0] 0
0 (0,5) → 0

Nessa produção, sempre que um "0" for encontrado durante a reescrita da string, haveria 50% de chance de que ela se comportasse como descrito anteriormente e 50% de chance de não mudar durante a produção. Quando uma gramática estocástica é usada em um contexto evolutivo , é aconselhável incorporar uma semente aleatória ao genótipo , para que as propriedades estocásticas da imagem permaneçam constantes entre as gerações.

Gramáticas sensíveis ao contexto

Uma regra de produção sensível ao contexto olha não apenas para o símbolo que está modificando, mas também para os símbolos na string que aparecem antes e depois dela. Por exemplo, a regra de produção:

b <a> c → aa

transforma "a" em "aa", mas apenas se o "a" ocorrer entre um "b" e um "c" na string de entrada:

... bac ...

Tal como acontece com as produções estocásticas, existem várias produções para lidar com símbolos em diferentes contextos. Se nenhuma regra de produção pode ser encontrada para um determinado contexto, a produção de identidade é assumida, e o símbolo não muda na transformação. Se as produções contextuais e livres de contexto existirem na mesma gramática, presume-se que a produção contextual tenha precedência quando aplicável.

Gramáticas paramétricas

Em uma gramática paramétrica, cada símbolo no alfabeto possui uma lista de parâmetros associada a ele. Um símbolo acoplado à sua lista de parâmetros é chamado de módulo, e uma string em uma gramática paramétrica é uma série de módulos. Um exemplo de string pode ser:

a (0,1) [b (0,0)] a (1,2)

Os parâmetros podem ser usados ​​pelas funções de desenho e também pelas regras de produção. As regras de produção podem usar os parâmetros de duas maneiras: primeiro, em uma instrução condicional que determina se a regra será aplicada e, segundo, a regra de produção pode modificar os parâmetros reais. Por exemplo, veja:

a (x, y): x == 0 → a (1, y + 1) b (2,3)

O módulo a (x, y) sofre transformação sob esta regra de produção se a condicional x = 0 for satisfeita. Por exemplo, um (0,2) sofreria transformação, e um (1,2) não.

Na parte de transformação da regra de produção, os parâmetros, bem como módulos inteiros, podem ser afetados. No exemplo acima, o módulo b (x, y) é adicionado à string, com os parâmetros iniciais (2,3). Além disso, os parâmetros do módulo já existente são transformados. Sob a regra de produção acima,

a (0,2)

Torna-se

a (1,3) b (2,3)

já que o parâmetro "x" de a (x, y) é explicitamente transformado em "1" e o parâmetro "y" de a é incrementado em um.

Gramáticas paramétricas permitem que comprimentos de linha e ângulos de ramificação sejam determinados pela gramática, ao invés dos métodos de interpretação da tartaruga. Além disso, se a idade for fornecida como um parâmetro para um módulo, as regras podem mudar dependendo da idade de um segmento da planta, permitindo a criação de animações de todo o ciclo de vida da árvore.

Gramáticas bidirecionais

O modelo bidirecional separa explicitamente o sistema de reescrita simbólica da atribuição de forma. Por exemplo, o processo de reescrita de string no Exemplo 2 (árvore fractal) é independente de como as operações gráficas são atribuídas aos símbolos. Em outras palavras, um número infinito de métodos de desenho são aplicáveis ​​a um determinado sistema de reescrita.

O modelo bidirecional consiste em 1) um processo progressivo constrói a árvore de derivação com regras de produção e 2) um processo regressivo realiza a árvore com formas de maneira gradual (das folhas à raiz). Cada etapa de derivação inversa envolve um raciocínio topológico geométrico essencial. Com essa estrutura bidirecional, as restrições e os objetivos do projeto são codificados na tradução da forma da gramática. Em aplicações de projeto arquitetônico, a gramática bidirecional apresenta conectividade interna consistente e uma rica hierarquia espacial.

Problemas abertos

Existem muitos problemas em aberto envolvendo estudos de sistemas L. Por exemplo:

  • Caracterização de todos os sistemas L livres de contexto determinísticos que são localmente catenativos . (Uma solução completa é conhecida apenas no caso em que existem apenas duas variáveis).
  • Dada uma estrutura, encontre um sistema L que possa produzir essa estrutura.

Tipos de sistemas L

Sistemas L na linha real R :

Os sistemas L bem conhecidos em um plano R 2 são:

Veja também

Notas

Livros

links externos

  1. ^ Pradal, Christophe; Fournier, cristão; Valduriez, Patrick; Cohen-Boulakia, Sarah (2015). OpenAlea: fluxos de trabalho científicos combinando análise de dados e simulação (PDF) . Anais da 27ª Conferência Internacional sobre Gerenciamento de Banco de Dados Científico e Estatístico - SSDBM '15 . p. 1. doi : 10.1145 / 2791347.2791365 . ISBN 9781450337090. S2CID  14246115 .
  2. ^ Boudon, Frédéric; Pradal, Christophe; Cokelaer, Thomas; Prusinkiewicz, Przemyslaw; Godin, Christophe (2012). "L-Py: Um Framework de Simulação de Sistema L para Modelagem de Desenvolvimento de Arquitetura de Plantas Baseado em uma Linguagem Dinâmica" . Frontiers in Plant Science . 3 : 76. doi : 10.3389 / fpls.2012.00076 . PMC  3362793 . PMID  22670147 .