Sistema L

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 pueden 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, una cadena de " axiomas " inicial 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 y botánico húngaro de la Universidad de Utrecht . ^[1] Lindenmayer usó sistemas L para describir el comportamiento de las células vegetales y para 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 ^{[2] y se pueden utilizar para generar}fractales autosimilares .

Orígenes

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. Más tarde, 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" lentamente y se vuelve más compleja. Los sistemas Lindenmayer también son populares en la generación de vida artificial .

Las gramáticas de sistemas 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 (el alfabeto ) es un conjunto de símbolos que contienen tanto elementos que pueden reemplazarse ( variables ) como aquellos que no pueden reemplazarse ("constantes" o "terminales").
ω ( inicio , axioma o iniciador ) es una cadena de símbolos de V que define el estado inicial del sistema.
P es un conjunto de reglas de producción o producciones que definen la forma en que las variables pueden reemplazarse con combinaciones de constantes y otras variables. Una producción consta de dos cadenas, la predecesora y la sucesora . Para cualquier símbolo A que sea miembro del conjunto V que no aparezca en el lado izquierdo de una producción en P, se supone la producción identidad A → A; estos símbolos se denominan constantes o terminales . (Véase Ley de identidad ).

Las reglas de la gramática del sistema L se aplican iterativamente comenzando desde el estado inicial. Se aplican tantas reglas como sea posible simultáneamente, 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, uno simplemente generaría una cadena en un lenguaje, y todas esas secuencias de aplicaciones producirían el lenguaje especificado por la gramática. Sin embargo, hay algunas cadenas en algunos lenguajes que no se pueden generar si la gramática se trata como un sistema L en lugar de una especificación de lenguaje. Por ejemplo, ^[3] supongamos que hay una regla S→SS en una gramática. Si las producciones se realizan una a la vez, comenzando desde 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, lo que nos daría SSSS. Por lo tanto, el conjunto de cadenas producidas por un L-sistema a partir de una gramática dada es un subconjunto del lenguaje formal definido por la gramática, y si tomamos un lenguaje como definido como un conjunto de cadenas, esto significa que un L-sistema dado es efectivamente un subconjunto del lenguaje formal definido por la gramática del L-sistema.

Un sistema L es independiente del contexto si cada regla de producción se refiere únicamente a un símbolo individual y no a sus vecinos. Por lo tanto, los sistemas L independientes del contexto se especifican mediante una gramática independiente del contexto . Si una regla depende no solo de un símbolo individual 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 del modelo hagan referencia a elementos de un dibujo en la pantalla de la computadora. Por ejemplo, el programa Fractint utiliza gráficos de tortuga (similares a los del lenguaje de programación Logo ) para producir imágenes en la pantalla. Interpreta cada constante en un modelo de sistema L como un comando de tortuga.

Ejemplos de sistemas L

Ejemplo 1: algas

Sistema L original de Lindenmayer para modelar el crecimiento de algas.

variables : AB

constantes : ninguna

axioma : 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 : ABAABABAABAAB

n = 6 : ABAABABAABAABAABAABABA

n = 7 : ABABABAABAABABAABABAABAABABAABAAB

Ejemplo 1: las algas, explicadas

n=0: Un inicio (axioma/iniciador) / \n=1: AB el único A inicial generado en AB por la regla (A → AB), la regla (B → A) no se pudo aplicar /| \n=2: ABA antigua cadena AB con todas las reglas aplicadas, A se volvió a generar en AB, antigua B se convirtió en A / | | | \n=3: ABAAB nota: todos los A producen una copia de sí mismos en primer lugar, luego una B, que se convierte... / | | | \ | \ \n=4: ABAABABA... en una A una generación después, comenzando a generar/repetir/recurrir 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 (omitiendo el primer 1, debido a nuestra elección del axioma):

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

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

Para cada cadena, si contamos la posición k desde el extremo izquierdo de la cadena, el valor se determina en función de si un múltiplo de la proporción áurea cae dentro del intervalo . La relación entre A y B también converge a la media áurea. ${\estilo de visualización (k-1,k)}$

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

Esta secuencia es una secuencia localmente catenativa porque , donde es la n -ésima generación. $G(n)=G(n-1)G(n-2)$ $G(n)$

Ejemplo 2: árbol fractal (binario)

variables : 0, 1
constantes : "[", "]"
axioma : 0
reglas : (1 → 11), (0 → 1[0]0)

La forma se construye introduciendo de forma recursiva 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 '[' permanece igual. 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 utilizando gráficos de tortugas , donde a cada símbolo se le asigna una operación gráfica que la tortuga debe realizar. Por ejemplo, en el ejemplo anterior, se le pueden dar a la tortuga las siguientes instrucciones:

0: dibuja un segmento de línea que termine en una hoja
1: dibuja un segmento de línea
[: empuje la posición y el ángulo, gire a la izquierda 45 grados
]: posición y ángulo de pop, girar a la derecha 45 grados

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

Axioma
Primera recursión
Segunda recursión
Tercera recursión
Cuarta recursión
Séptima recursión, reducida diez veces

Ejemplo 3: Conjunto de Cantor

variables : AB

constantes : ninguna

inicio : Una {cadena de caracteres inicial}

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

Sea A "avanzar" y B "moverse hacia adelante".

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 utiliza sólo ángulos rectos.

variables : F

constantes : + −

Inicio : F

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

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

n = 0:

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+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

Ejemplo 5: triángulo de Sierpinski

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

variables : FG

constantes : + −

Inicio : F−G−G

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

ángulo : 120°

Aquí, F y G significan "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 : AB

constantes : + −

comienzo :A

reglas : (A → B−A−B), (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 ).

Evolución para n = 2, n = 4, n = 6, n = 8

Ejemplo 6: curva de dragón

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

variables : FG

constantes : + −

Inicio : F

Reglas : (F → F+G), (G → FG)

ángulo : 90°

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

Curva del dragón para n = 10

Ejemplo 7: planta fractal

variables : XF

constantes : + − [ ]

Inicio : X

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

ángulo : 25°

Primero, debe inicializar una pila vacía. Esto sigue el método LIFO (último en entrar, primero en salir) para agregar y eliminar elementos. Aquí, F significa "dibujar hacia adelante", − significa "girar a la derecha 25°" y + significa "girar a la izquierda 25°". 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, por lo que empuja la posición y el ángulo a la parte superior de la pila, cuando se encuentra el token "]", saca la pila y restablece la posición y el ángulo. Cada "[" viene antes de cada token "]".

Planta fractal para n =6

Variaciones

Se han desarrollado varias elaboraciones de esta técnica básica del sistema L que pueden utilizarse en conjunto. Entre ellas 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 gramatical que hemos analizado 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, dándole 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

En el marco de esta producción, siempre que se encuentre un "0" durante la reescritura de una cadena, 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 en el genotipo , de modo que las propiedades estocásticas de la imagen permanezcan constantes entre generaciones.

Gramáticas sensibles al contexto

Una regla de producción sensible al contexto no solo tiene en cuenta el símbolo que modifica, sino también los símbolos de la cadena que aparecen antes y después de él. Por ejemplo, la regla de producción:

b < a > c → aa

transforma "a" en "aa", pero sólo si la "a" aparece entre una "b" y una "c" en la cadena de entrada:

…de vuelta…

Al igual que con las producciones estocásticas, existen múltiples producciones para manejar símbolos en diferentes contextos. Si no se puede encontrar ninguna regla de producción para un contexto determinado, se supone la producción de identidad y el símbolo no cambia en la transformación. Si existen producciones sensibles al contexto y libres de contexto dentro de la misma gramática, se supone que la producción sensible al contexto tiene prioridad cuando es 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 acoplado a su lista de parámetros se denomina módulo, y una cadena en una gramática paramétrica es una serie de módulos. Un ejemplo de cadena 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 utilizar 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, observe lo siguiente:

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

El módulo a(x,y) sufre una transformación según esta regla de producción si se cumple la condición 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, se pueden afectar tanto los parámetros como los módulos completos. En el ejemplo anterior, se agrega el módulo b(x,y) a la cadena, con parámetros iniciales (2,3). Además, se transforman los parámetros del módulo ya existente. Según la regla de producción anterior,

un(0,2)

Se convierte en

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

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

Las gramáticas paramétricas permiten determinar las longitudes de las líneas y los ángulos de ramificación mediante la gramática, en lugar de los métodos de interpretación de la tortuga. 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, una cantidad infinita de métodos de dibujo son aplicables a un sistema de reescritura determinado.

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

Problemas abiertos

Existen muchos problemas abiertos relacionados con el estudio de los sistemas L. Por ejemplo:

Caracterización de todos los sistemas L deterministas libres de contexto que son localmente catenativos . (Una solución completa se conoce solo en el caso en que solo hay dos variables). ^[5]
Dada una estructura, encuentre un sistema L que pueda producir esa estructura. ^{[ cita requerida ]}

Tipos de sistemas L

Sistemas L sobre la recta real R :

Sistema Prouhet-Thue-Morse

Los sistemas L más conocidos en un plano R ² son:

curvas que llenan el espacio ( curva de Hilbert , curvas de Peano , curva de Dekking, curvas de Kolam ),
curvas medianas que llenan el espacio ( curva C de Lévy , curva del dragón de Harter-Heighway , terdragón de Davis-Knuth),
mosaicos ( mosaicos de esfinge , mosaicos de Penrose )

Véase también

Wikimedia Commons alberga una categoría multimedia sobre Sistemas L.

Morfogénesis digital
Fractal
Sistema de funciones iteradas
Curva de Hilbert
Sistema de reacción-difusión : tipo de modelo matemático que proporciona simulaciones de reactivos químicos difusores (incluidas las de tipo Life-like)
Gramática estocástica independiente del contexto
Árbol de velocidad
La belleza algorítmica de las plantas

Notas

^ Lindenmayer, Aristid (marzo de 1968). "Modelos matemáticos para interacciones celulares en el desarrollo II. Filamentos simples y ramificados con entradas bilaterales". Journal of Theoretical Biology . 18 (3): 300–315. Bibcode :1968JThBi..18..300L. doi :10.1016/0022-5193(68)90080-5. ISSN 0022-5193. PMID 5659072.
^ Grzegorz Rozenberg y Arto Salomaa. La teoría matemática de los sistemas L (Academic Press, Nueva York, 1980). ISBN 0-12-597140-0
^ "Sistemas L". Enciclopedia de Matemáticas . Springer . Consultado el 26 de julio de 2022 .
^ Hua, H., diciembre de 2017. Un modelo procedimental bidireccional para el diseño arquitectónico. En Computer Graphics Forum (vol. 36, n.º 8, págs. 219-231).
^ Kari, Lila; Rozenberg, Grzegorz; Salomaa, Arto (1997). "Sistemas L". Manual de lenguajes formales . págs. 253–328. doi :10.1007/978-3-642-59136-5_5. ISBN 978-3-642-63863-3.

Libros

Przemysław Prusinkiewicz , Aristid Lindenmayer – La belleza algorítmica de las plantas Versión en PDF disponible aquí de forma gratuita Archivado el 10 de abril de 2021 en Wayback Machine
Grzegorz Rozenberg , Arto Salomaa – Sistemas Lindenmayer: Impactos en la informática teórica, los gráficos por computadora y la biología del desarrollo ISBN 978-3-540-55320-5
DS Ebert, FK Musgrave, et al. – Texturizado y modelado: un enfoque procedimental , ISBN 0-12-228730-4
Burry, Jane, Burry Mark, (2010). Las nuevas matemáticas de la arquitectura, Nueva York: Thames and Hudson.
Aristid Lindenmayer, "Modelos matemáticos para la interacción celular en el desarrollo". J. Theoret. Biology, 18:280—315, 1968.

Enlaces externos

Botánica algorítmica en la Universidad de Calgary
L-Systems: Una página fácil de usar para generar fractales y plantas a partir de L-Systems.
Ramificación: Árbol del sistema L Una aplicación Java y su código fuente ( código abierto ) de la simulación del crecimiento del árbol botánico utilizando el sistema L.
Fractales verdaderos del sistema L de Fractint
OpenAlea Archivado el 17 de octubre de 2005 en Wayback Machine : un entorno de software de código abierto para modelado de plantas, ^[1] que contiene L-Py, una implementación de Python de código abierto de los sistemas Lindenmayer ^[2]
"powerPlant", un software de modelado de paisajes de código abierto
Página de inicio de Fractint
Un generador de sistemas L simple (Windows)
Lyndyhop: otro generador de sistemas L simple (Windows y Mac)
Un generador evolutivo de sistemas L (anyos*)
Una implementación de sistemas L en Racket
Griffiths, Dave (2004). "LsystemComposition". Pawfal . Archivado desde el original el 2004-11-06 . Consultado el 2012-04-19 .Página sobre el uso de sistemas L y algoritmos genéticos para generar música.
eXtended L-Systems (XL), gramáticas de crecimiento relacional y plataforma de software de código abierto GroIMP.
Una aplicación JAVA con muchas figuras fractales generadas por sistemas L. Archivado el 6 de agosto de 2016 en Wayback Machine.
My Graphics: una aplicación para iPhone/iPad que genera varios patrones gráficos del sistema L.
Manousakis, Stelios (junio de 2006). Musical L-Systems (PDF) (Tesis de maestría). Conservatorio Real de La Haya . Archivado (PDF) desde el original el 23 de julio de 2011. Consultado el 19 de julio de 2022 .
Experimentos en línea con L-Systems utilizando JSXGraph (JavaScript)
Flea Una implementación Ruby de LSYSTEM, que utiliza un lenguaje específico de dominio en lugar de comandos generadores concisos
Planta de energía Lindenmayer y generador fractal utilizando sistemas L (JavaScript)
Rozenberg, G.; Salomaa, A. (2001) [1994], "Sistemas L", Enciclopedia de Matemáticas , EMS Press
L-Parser de Laurens Lapré Archivado el 13 de septiembre de 2013 en Wayback Machine
Sistemas L HTML5: realice experimentos en línea
El programa de gráficos vectoriales Inkscape cuenta con un analizador L-System
Liou, Cheng-Yuan; Wu, Tai-Hei; Lee, Chia-Ying (2009). "Modelado de la complejidad en el ritmo musical". Complejidad . 15 (4): 19–30. doi :10.1002/cplx.20291. S2CID 18737938.
Una implementación de un analizador sintáctico del sistema L y gráficos de tortuga simples en el lenguaje de programación Icon
Un generador de sistema Lindenmeyer de Nolan Carroll
Bloogen: sistemas L con un toque genético

^ Pradal, Christophe; Fournier, Christian; Valduriez, Patrick; Cohen-Boulakia, Sarah (2015). "OpenAlea". Actas de la 27.ª Conferencia internacional sobre gestión de bases de datos científicas y estadísticas (PDF) . págs. 1–6. doi :10.1145/2791347.2791365. ISBN. 9781450337090. S2CID 14246115. Archivado (PDF) del original el 17 de octubre de 2019.
^ Boudon, Frédéric; Pradal, Christophe; Cokelaer, Thomas; Prusinkiewicz, Przemyslaw; Godin, Christophe (2012). "L-Py: Un marco de simulación de sistemas L para el desarrollo de la arquitectura de plantas basado en un lenguaje dinámico". Frontiers in Plant Science . 3 : 76. doi : 10.3389/fpls.2012.00076 . PMC 3362793 . PMID 22670147.