Sistema L

Los árboles del sistema L forman modelos realistas de patrones naturales

Un sistema L o sistema Lindenmayer es un sistema de reescritura paralela y un tipo de gramática formal. Un sistema L consiste en un alfabeto de símbolos que se puede usar para hacer cadenas, una colección de reglas de producción que expanden cada símbolo en una cadena más grande de símbolos, un "axioma" cadena a partir de la cual comenzar la construcción, y un mecanismo para traducir las cadenas generadas en estructuras geométricas. Los sistemas L fueron introducidos y desarrollados en 1968 por Aristid Lindenmayer, un biólogo teórico húngaro y botánico de la Universidad de Utrecht. Lindenmayer utilizó sistemas L para describir el comportamiento de las células vegetales y modelar los procesos de crecimiento del desarrollo de las plantas. Los sistemas L también se han utilizado para modelar la morfología de una variedad de organismos y se pueden utilizar para generar fractales autosimilares.

Orígenes

"Weeds", generado usando un sistema L en 3D.

Como biólogo, Lindenmayer trabajó con levaduras y hongos filamentosos y estudió los patrones de crecimiento de varios tipos de bacterias, como la cianobacteria Anabaena catenula. Originalmente, los sistemas L se idearon para proporcionar una descripción formal del desarrollo de estos organismos multicelulares simples y para ilustrar las relaciones de vecindad entre las células vegetales. Posteriormente, este sistema se amplió para describir plantas superiores y estructuras ramificadas complejas.

Estructura del sistema L

La naturaleza recursiva de las reglas del sistema L conduce a la autosimilitud y, por lo tanto, las formas de tipo fractal son fáciles de describir con un sistema L. Los modelos de plantas y las formas orgánicas de aspecto natural son fáciles de definir, ya que al aumentar el nivel de recursión, la forma 'crece' y se vuelve más complejo. Los sistemas de Lindenmayer también son populares en la generación de vida artificial.

Las gramáticas del sistema L son muy similares a la gramática semi-Thue (ver jerarquía de Chomsky). Los sistemas L ahora se conocen comúnmente como sistemas L paramétricos, definidos como una tupla

G =V, ω, P),

dónde

• V (alfabeto) es un conjunto de símbolos que contienen ambos elementos que pueden ser reemplazados (variables) y aquellos que no pueden ser reemplazados ("constantes" o "terminales")
• ⋅ ()Empieza, axiom o iniciador) es una cadena de símbolos de V definir el estado inicial del sistema
• P es un conjunto de Normas de producción o producciones definir la forma en que las variables pueden ser reemplazadas con combinaciones de constantes y otras variables. Una producción consiste en dos cuerdas, la predecesor y el sucesor. Para cualquier símbolo A que es miembro del conjunto V que no aparece en la mano izquierda de una producción en P, se asume la producción de identidad A → A; estos símbolos se llaman constantes o terminales. (Véase Ley de identidad).

Las reglas de la gramática del sistema L se aplican iterativamente a partir del estado inicial. Se aplican simultáneamente tantas reglas como sea posible, por iteración. El hecho de que cada iteración emplee tantas reglas como sea posible diferencia un sistema L de un lenguaje formal generado por una gramática formal, que aplica solo una regla por iteración. Si las reglas de producción se aplicaran solo una a la vez, simplemente se generaría una cadena en un idioma, y todas esas secuencias de aplicaciones producirían el idioma especificado por la gramática. Sin embargo, hay algunas cadenas en algunos idiomas que no se pueden generar si la gramática se trata como un sistema L en lugar de una especificación de idioma. Por ejemplo, supongamos que hay una regla S→SS en una gramática. Si las producciones se realizan de una en una, entonces a partir de S, podemos obtener primero SS, y luego, aplicando la regla nuevamente, SSS. Sin embargo, si todas las reglas aplicables se aplican en cada paso, como en un sistema L, entonces no podemos obtener esta forma oracional. En cambio, el primer paso nos daría SS, pero el segundo aplicaría la regla dos veces, dándonos SSSS. Así, el conjunto de cadenas producido por un sistema L a partir de una gramática dada es un subconjunto del lenguaje formal definido por la gramática, y si tomamos un lenguaje para ser definido como un conjunto de cadenas, esto significa que un L- El sistema es efectivamente un subconjunto del lenguaje formal definido por la gramática del sistema L.

Un sistema L es libre de contexto si cada regla de producción se refiere solo a un símbolo individual y no a sus vecinos. Los sistemas L independientes del contexto se especifican, por tanto, mediante una gramática independiente del contexto. Si una regla depende no solo de un solo símbolo sino también de sus vecinos, se denomina sistema L sensible al contexto.

Si hay exactamente una producción para cada símbolo, entonces se dice que el sistema L es determinista (un sistema L determinista libre de contexto se denomina popularmente sistema D0L). Si hay varios, y cada uno se elige con una cierta probabilidad durante cada iteración, entonces es un sistema L estocástico.

El uso de sistemas L para generar imágenes gráficas requiere que los símbolos en el modelo se refieran a elementos de un dibujo en la pantalla de la computadora. Por ejemplo, el programa Fractint utiliza gráficos de tortugas (similares a los del lenguaje de programación Logo) para producir imágenes de pantalla. Interpreta cada constante en un modelo de sistema L como un comando de tortuga.

Ejemplos de sistemas L

Ejemplo 1: Algas

El sistema L original de Lindenmayer para modelar el crecimiento de algas.

variables: A B

constantesNo.

axiom A

reglas: (A → AB), (B → A)

que produce:

n = 0: A

n = 1: AB

n = 2: ABA

n = 3: ABAAB

n = 4: ABAABABA

n = 5: ABAABAABAAB

n = 6: ABAABAABAABAABA

n = 7: ABAABAABAABAABABAABAABABABAABA

Ejemplo 1: Algas, explicadas

n=0: Un comienzo (axiom/initiator)
/ 
n=1: A B el single inicial A se despertó en AB por regla (A → AB), regla (B → A) no se podía aplicar
/ invitación 
n=2: A B Una antigua cadena AB con todas las reglas aplicadas, A desovecido en AB de nuevo, anterior B convertido en A
/ TENIDO TERRITORIO TENIDO
n=3: A B A A B nota todo A está produciendo una copia de sí mismos en primer lugar, luego una B, que gira...
/ TEN TENIDO TENIDO TENENCIA  
n=4: A B A A B A A... en una generación A más tarde, empezando a desovecer/repeat/recurse entonces

El resultado es la secuencia de palabras de Fibonacci. Si contamos la longitud de cada cadena, obtenemos la famosa secuencia de números de Fibonacci (saltándonos el primer 1, debido a nuestra elección de axioma):

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

Si no queremos omitir el primer 1, podemos usar el axioma B. Eso colocaría el nodo B antes del nodo superior (A) del gráfico anterior.

Para cada cuerda, si contamos la k-la posición desde el extremo izquierdo de la cadena, el valor se determina por si un múltiplo de la relación de oro cae dentro del intervalo ()k− − 1,k){displaystyle (k-1,k)}. La proporción de A a B coincide igualmente con la media dorada.

Este ejemplo arroja el mismo resultado (en términos de la longitud de cada cadena, no la secuencia de As y Bs) si la regla ( A → AB) se reemplaza por (A → BA), excepto que las cadenas se reflejan.

Esta secuencia es una secuencia localmente catentiva porque G()n)=G()n− − 1)G()n− − 2){displaystyle G(n)=G(n-1)G(n-2)}, donde G()n){displaystyle G(n)} es n-a generación.

Ejemplo 2: Árbol fractal (binario)

• variables: 0, 1
• constantes: “[, “]”
• axiom: 0
• reglas: (1 → 11), (0 → 1[0]0)

La forma se construye alimentando recursivamente el axioma a través de las reglas de producción. Cada carácter de la cadena de entrada se compara con la lista de reglas para determinar con qué carácter o cadena se debe reemplazar en la cadena de salida. En este ejemplo, un '1' en la cadena de entrada se convierte en '11' en la cadena de salida, mientras que '[' sigue siendo el mismo. Aplicando esto al axioma de '0', obtenemos:

Podemos ver que esta cadena crece rápidamente en tamaño y complejidad. Esta cadena se puede dibujar como una imagen usando gráficos de tortuga, donde a cada símbolo se le asigna una operación gráfica para que la tortuga la realice. Por ejemplo, en el ejemplo anterior, a la tortuga se le pueden dar las siguientes instrucciones:

• 0: dibujar un segmento de línea que termina en una hoja
• 1: dibujar un segmento de línea
• [: posición de empuje y ángulo, gire a la izquierda 45 grados
• ]: Posición pop y ángulo, gire a la derecha 45 grados

Pulsar y pop se refieren a una pila LIFO (una gramática más técnica tendría símbolos separados para "pulsar posición" y "girar a la izquierda"). Cuando la interpretación de la tortuga encuentra un '[', la posición y el ángulo actuales se guardan y luego se restauran cuando la interpretación encuentra un ']'. Si se han "empujado múltiples valores," luego un "pop" restaura los valores guardados más recientemente. Aplicando las reglas gráficas enumeradas anteriormente a la recursividad anterior, obtenemos:

Ejemplo 3: Conjunto de Cantor

variables: A B

constantesNo.

Empieza: Una cadena de caracteres increíble.

reglas: (A → ABA), (B → BBB)

Que A signifique "atraer hacia adelante" y B significan "avanzar".

Esto produce el famoso conjunto fractal de Cantor en una línea recta real R.

Ejemplo 4: Curva de Koch

Una variante de la curva de Koch que usa solo ángulos rectos.

variables: F

constantes: + −

Empieza: F

reglas: (F → F+F−F−F+F)

Aquí, F significa "avanzar", + significa "girar 90° a la izquierda" y − significa "girar 90° a la derecha" (ver gráficos de tortugas).

n = 0:

F

n = 1:

F+F−F−F+F

n = 2:

F+F –F+F+F –F+F –F+F –F+F –F+F –F+F –F+F –F+F+F –F

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

Ejemplo 5: Triángulo de Sierpinski

El triángulo de Sierpinski dibujado usando un sistema L.

variables: F G

constantes: + −

Empieza F−G−G

reglas: (F → F−G+F+G−F), (G → GG)

ángulo: 120°

Aquí, F significa "avanzar", G significa "avanzar", + significa "girar a la izquierda en ángulo" y − significa " girar a la derecha en ángulo".

• 

  n = 2

• 

  n = 4

• 

  n = 6

También es posible aproximar el triángulo de Sierpinski utilizando un sistema L de curva de punta de flecha de Sierpinski.

variables: A B

constantes: + −

Empieza A

reglas: (A → B−AB), (B → A+B+A)

ángulo: 60°

Aquí, A y B significan "avanzar", + significa "girar a la izquierda en ángulo" y − significa "girar a la derecha en ángulo" (ver gráficos de tortugas).

Ejemplo 6: Curva de dragón

La curva del dragón dibujada usando un sistema L.

variables: F G

constantes: + −

Empieza: F

reglas: (F → F+G), (G → F-G)

ángulo: 90°

Aquí, F y G significan "avanzar", + significa "girar un ángulo a la izquierda" y − significa "girar un ángulo a la derecha".

Ejemplo 7: Planta fractal

variablesX F

constantes: + − [ ]

Empieza: X

reglas: (X → F+[X]-X]-F[-FX]+X), (F → FF)

ángulo: 25°

Aquí, F significa "avanzar", − significa "girar 25° a la derecha" y + significa "girar 25° a la izquierda". X no corresponde a ninguna acción de dibujo y se utiliza para controlar la evolución de la curva. El corchete "[" corresponde a guardar los valores actuales de posición y ángulo, que se restablecen cuando el correspondiente "]" es ejecutado.

Variaciones

Se han desarrollado varias elaboraciones sobre esta técnica básica del sistema L que se pueden usar en conjunto. Entre estos se encuentran las gramáticas estocásticas, las gramáticas sensibles al contexto y las gramáticas paramétricas.

Gramáticas estocásticas

El modelo de gramática que hemos discutido hasta ahora ha sido determinista, es decir, dado cualquier símbolo en el alfabeto de la gramática, ha habido exactamente una regla de producción, que siempre se elige y siempre realiza la misma conversión. Una alternativa es especificar más de una regla de producción para un símbolo, dando a cada una una probabilidad de ocurrencia. Por ejemplo, en la gramática del Ejemplo 2, podríamos cambiar la regla para reescribir "0" de:

0 → 1[0]0

a una regla probabilística:

0 (0.5) → 1[0]0

0 (0.5) → 0

Bajo esta producción, cada vez que un "0" se encuentra durante la reescritura de cadenas, habría un 50 % de posibilidades de que se comportara como se describió anteriormente y un 50 % de posibilidades de que no cambiara durante la producción. Cuando se utiliza una gramática estocástica en un contexto evolutivo, es recomendable incorporar una semilla aleatoria al genotipo, para que las propiedades estocásticas de la imagen se mantengan constantes entre generaciones.

Gramáticas sensibles al contexto

Una regla de producción sensible al contexto observa no solo el símbolo que está modificando, sino también los símbolos de la cadena que aparecen antes y después. Por ejemplo, la regla de producción:

b

transforma "a" a "aa", pero solo si el "a" ocurre entre una "b" y una "c" en la cadena de entrada:

...bac...

Al igual que con las producciones estocásticas, existen múltiples producciones para manejar símbolos en diferentes contextos. Si no se puede encontrar una regla de producción para un contexto dado, se asume la producción de identidad y el símbolo no cambia en la transformación. Si existen producciones sensibles al contexto y sin contexto dentro de la misma gramática, se supone que la producción sensible al contexto tiene prioridad cuando sea aplicable.

Gramáticas paramétricas

En una gramática paramétrica, cada símbolo del alfabeto tiene una lista de parámetros asociada. Un símbolo junto con su lista de parámetros se denomina módulo, y una cadena en una gramática paramétrica es una serie de módulos. Una cadena de ejemplo podría ser:

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

Los parámetros pueden ser utilizados por las funciones de dibujo y también por las reglas de producción. Las reglas de producción pueden usar los parámetros de dos maneras: primero, en una declaración condicional que determina si se aplicará la regla y, segundo, la regla de producción puede modificar los parámetros reales. Por ejemplo, mira:

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

El módulo a(x,y) se transforma bajo esta regla de producción si se cumple el condicional x=0. Por ejemplo, a(0,2) sufriría una transformación y a(1,2) no.

En la parte de transformación de la regla de producción, los parámetros y módulos completos pueden verse afectados. En el ejemplo anterior, el módulo b(x,y) se agrega a la cadena, con parámetros iniciales (2,3). Además, se transforman los parámetros del módulo ya existente. Bajo la regla de producción anterior,

a(0,2)

Se convierte

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

como la "x" parámetro de a(x,y) se transforma explícitamente en "1" y la "y" el parámetro de a se incrementa en uno.

Las gramáticas paramétricas permiten que las longitudes de las líneas y los ángulos de ramificación sean determinados por la gramática, en lugar de los métodos de interpretación de las tortugas. Además, si se proporciona la edad como parámetro para un módulo, las reglas pueden cambiar según la edad de un segmento de la planta, lo que permite crear animaciones de todo el ciclo de vida del árbol.

Gramáticas bidireccionales

El modelo bidireccional separa explícitamente el sistema de reescritura simbólica de la asignación de formas. Por ejemplo, el proceso de reescritura de cadenas en el Ejemplo 2 (árbol fractal) es independiente de cómo se asignan las operaciones gráficas a los símbolos. En otras palabras, un número infinito de métodos de dibujo son aplicables a un sistema de reescritura dado.

El modelo bidireccional consta de 1) un proceso hacia adelante construye el árbol de derivación con reglas de producción, y 2) un proceso hacia atrás realiza el árbol con formas paso a paso (desde las hojas hasta la raíz). Cada paso de derivación inversa implica un razonamiento geométrico-topológico esencial. Con este marco bidireccional, las restricciones de diseño y los objetivos se codifican en la traducción de forma gramatical. En las aplicaciones de diseño arquitectónico, la gramática bidireccional presenta una conectividad interior constante y una rica jerarquía espacial.

Problemas abiertos

Hay muchos problemas abiertos relacionados con estudios de sistemas L. Por ejemplo:

• Caracterización de todos los sistemas L libres de contexto determinísticos que son localmente catentivos. (Una solución completa se conoce sólo en el caso en que sólo hay dos variables).
• Dada una estructura, encuentra un sistema L que puede producir esa estructura.

Tipos de sistemas L

Sistemas L en la línea real R:

• Sistema Prouhet-Thue-Morse

Los sistemas L conocidos en un plano R² son:

• curvas de llenado de espacio (Hilbert curva, Peano's curvas, Dekking's church, kolams),
• curvas medianas de llenado de espacio (Lévy C curva, Harter-Heighway dragón curva, Davis-Knuth terdragon),
• baldosas (sphinx tiling, Penrose tiling)

Libros

• Przemysław Prusinkiewicz, Aristid Lindenmayer – The Algorithmic Beauty of Plants versión en PDF disponible aquí gratis
• Grzegorz Rozenberg, Arto Salomaa – Lindenmayer Systems: Impactos en la Ciencia Teórica de la Computación, Gráficos de Computación y Biología del Desarrollo ISBN 978-3-540-55320-5
• D.S. Ebert, F.K. Musgrave, et al. – Textura y modelado: A Procedural Approach, ISBN 0-12-228730-4
• Burry, Jane, Burry Mark, (2010). Las Nuevas Matemáticas de Arquitectura, Nueva York: Támesis y Hudson.
• Aristid Lindenmayer, "Modelos matemáticos para la interacción celular en el desarrollo". J. Theoret. Biología, 18:280-315, 1968.