sistema L

Sistema de reescritura y tipo de gramática formal.

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

Un sistema L o sistema Lindenmayer es un sistema de reescritura paralelo y un tipo de gramática formal . Un sistema L consta de un alfabeto de símbolos que se pueden utilizar para formar cadenas , una colección de reglas de producción que expanden cada símbolo en una cadena de símbolos más grande, una cadena " axioma " 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 , biólogo teórico y botánico húngaro de la Universidad de Utrecht . ^[1] 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 ^{[2] y pueden usarse para generar} fractales autosemejantes .

Orígenes

'Weeds', generada mediante 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 organismos multicelulares tan simples e ilustrar las relaciones de vecindad entre 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 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 recursividad 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 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

GRAMO = ( V , ω, P ),

dónde

• V (el alfabeto ) es un conjunto de símbolos que contienen tanto elementos que pueden ser reemplazados ( variables ) como aquellos que no pueden ser reemplazados ("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 llaman constantes o terminales . (Ver Ley de identidad ).

Las reglas de la gramática del sistema L se aplican de forma iterativa a partir del 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 sólo una regla por iteración. Si las reglas de producción se aplicaran sólo una a la vez, simplemente se 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 idiomas que no se pueden generar si la gramática se trata como un sistema L en lugar de una especificación del idioma. Por ejemplo, ^[3] supongamos que hay una regla S→SS en una gramática. Si las producciones se hacen de una en una, entonces partiendo de S, podemos obtener primero SS, y luego, aplicando nuevamente la regla, SSS. Sin embargo, si se aplican todas las reglas aplicables 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 producidas 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 definido como un conjunto de cadenas, esto significa que un L-sistema dado El sistema es efectivamente un subconjunto del lenguaje formal definido por la gramática del sistema L.

Un sistema L está libre de contexto si cada regla de producción se refiere sólo a un símbolo individual y no a sus vecinos. Por tanto, los sistemas L libres de contexto se especifican mediante una gramática libre de contexto . Si una regla depende no sólo de un único 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 hagan referencia 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  : AB

constantes  : ninguna

axioma  : A

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

que produce:

norte = 0 : Un

norte = 1 : AB

norte = 2 : ABA

n = 3 : ABAAB

n = 4 : ABABABA

n = 5 : ABABABAABAAB

n = 6 : ABABABAABAABABAABABA

n = 7 : ABABABAABAABABAABABAABAABABAABAAB

Ejemplo 1: algas, explicadas

n=0: Un comienzo (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 generó nuevamente AB, la antigua B se convirtió en A / | | | \n=3: ABAAB nota que todos los A producen una copia de sí mismos en primer lugar, luego un B, que se convierte... / | | | \ | \ \n=4: ABAABABA... en una A una generación más tarde, comenzando a generar/repetir/recurrir luego

El resultado es la secuencia de palabras de Fibonacci . Si contamos la longitud de cada cuerda, obtenemos la famosa secuencia de números de Fibonacci (omitándonos 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 primero, podemos usar el axioma B. Eso colocaría el nodo B antes del nodo superior ( A ) del gráfico anterior.

Para cada cadena, si contamos la k -ésima posición 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 proporción entre A y B también converge hacia la media áurea. ${\displaystyle (k-1,k)}$

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

Esta secuencia es una secuencia catenativa local porque donde está la enésima generación. ${\displaystyle G(n)=G(n-1)G(n-2)}$ ${\displaystyle G(n)}$

Ejemplo 2: árbol fractal (binario)

• variables  : 0, 1
• constantes : "[", "]"
• axioma  : 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 reemplazarlo 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 utilizando gráficos de tortuga , donde a cada símbolo se le asigna una operación gráfica que debe realizar la tortuga. Por ejemplo, en el ejemplo anterior, a la tortuga se le pueden dar las siguientes instrucciones:

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

Push y pop se refieren a una pila LIFO (una gramática más técnica tendría símbolos separados para "empujar 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 "enviado" varios valores, entonces un "pop" restaura los valores guardados más recientemente. Aplicando las reglas gráficas enumeradas anteriormente a la recursividad anterior, obtenemos:

• 
  Axioma
• 
  Primera recursividad
• 
  Segunda recursividad
• 
  Tercera recursión
• 
  Cuarta recursividad
• 
  Séptima recursividad, 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 significa "avanzar" y B significa "avanzar".

Esto produce el famoso conjunto fractal de Cantor sobre 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 ).

norte = 0:

F

norte = 1:

F+F−F−F+F

norte = 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

norte = 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

Ejemplo 5: triángulo de Sierpinski

El triángulo de Sierpinski dibujado mediante 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".

• 
  norte = 2
• 
  norte = 4
• 
  norte = 6

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

variables  : AB

constantes  : + −

empezar  un

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 del dragón

La curva del dragón dibujada usando 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 necesitas 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 "avanzar", − 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 para la posición y el ángulo, por lo que empuja la posición y el ángulo a la parte superior de la pila, cuando se encuentra el token "]", abre 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 una serie de elaboraciones sobre esta técnica básica del sistema L que se pueden utilizar 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 ocurrir. 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 esta producción, siempre que se encuentre un "0" durante la reescritura de una cadena, habrá un 50 % de posibilidades de que se comporte como se describió anteriormente y un 50 % de posibilidades de que no cambie durante la producción. Cuando se utiliza una gramática estocástica en un contexto evolutivo , es recomendable incorporar al genotipo una semilla aleatoria , de modo 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 analiza no sólo el símbolo que está modificando, 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:

…volver…

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 dado, se supone la producción de identidad y el símbolo no cambia en la transformación. Si dentro de la misma gramática existen producciones sensibles al contexto y libres de contexto, 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 la regla se aplicará y, segundo, la regla de producción puede modificar los parámetros reales. Por ejemplo, mire:

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

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

En la parte de transformación de la regla de producción, los parámetros y también 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. Según la regla de producción anterior,

un(0,2)

se convierte

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

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

Las gramáticas paramétricas permiten que la longitud de las líneas y los ángulos de ramificación sean determinados por la gramática, en lugar de por los métodos de interpretación de la tortuga. Además, si la edad se proporciona como parámetro para un módulo, las reglas pueden cambiar dependiendo de la edad de un segmento de 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 determinado.

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 de manera gradual (desde las hojas hasta la raíz). Cada paso de derivación inversa implica un razonamiento topológico geométrico esencial. Con este marco bidireccional, las limitaciones y objetivos del diseño se codifican en la traducción de forma gramatical. En aplicaciones de diseño arquitectónico, la gramática bidireccional presenta una conectividad interior consistente y una rica jerarquía espacial. ^[4]

Problemas abiertos

Hay muchos problemas abiertos que involucran estudios de sistemas L. Por ejemplo:

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

Tipos de sistemas L

Sistemas L en la línea real R :

• Sistema Prouhet-Thue-Morse

Los sistemas L bien conocidos en un avión R ² son:

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

Ver también

• Morfogénesis digital
• fractales
• 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 en difusión (incluido el real)
• Gramática estocástica libre de contexto
• Árbol de velocidad
• La belleza algorítmica de las plantas

Notas

1. Lindenmayer, Aristid (marzo de 1968). "Modelos matemáticos de interacciones celulares en el desarrollo II. Filamentos simples y ramificados con entradas bilaterales". Revista de Biología Teórica . 18 (3): 300–315. Código Bib : 1968JThBi..18..300L. doi :10.1016/0022-5193(68)90080-5. ISSN  0022-5193. PMID  5659072.
2. Grzegorz Rozenberg y Arto Salomaa. La teoría matemática de los sistemas L (Academic Press, Nueva York, 1980). ISBN 0-12-597140-0 
3. "Sistemas L". Enciclopedia de Matemáticas . Saltador . Consultado el 26 de julio de 2022 .
4. Hua, H., diciembre de 2017. Un modelo procesal bidireccional para el diseño arquitectónico. En Computer Graphics Forum (Vol. 36, No. 8, págs. 219-231).
5. 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 - Lindenmayer Systems: 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 y otros. – Texturizado y modelado: un enfoque procesal , 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 de interacción celular en el desarrollo". J. Teórico. Biología, 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 Un subprograma de Java y su código fuente ( código abierto ) de la simulación del crecimiento del árbol botánico utilizando el sistema L.
• Fractint L-System Fractales verdaderos
• 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 simple de sistemas L (Windows y Mac)
• Un generador de sistemas L evolutivo (anyos*)
• Una implementación de sistemas L en Racket
• Griffiths, Dave (2004). "Composición del sistema L". Pawfal . Archivado desde el original el 6 de noviembre de 2004 . Consultado el 19 de abril de 2012 .Página sobre el uso de sistemas L y algoritmos genéticos para generar música.
• eXtended L-Systems (XL), Relational Growth Grammars y la plataforma de software de código abierto GroIMP.
• Un subprograma JAVA con muchas figuras fractales generadas por L-systems. Archivado el 6 de agosto de 2016 en Wayback Machine.
• My Graphics: una aplicación para iPhone/iPad que genera varios patrones de gráficos del sistema L.
• Manousakis, Stelios (junio de 2006). Musical L-Systems (PDF) (Tesis de maestría). Real Conservatorio 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 usando JSXGraph (JavaScript)
• Flea Una implementación Ruby de LSYSTEM, que utiliza un lenguaje específico de dominio en lugar de comandos generadores concisos
• Lindenmayer power Una planta y un generador fractal usando sistemas L (JavaScript)
• Rozenberg, G.; Salomaa, A. (2001) [1994], "L-systems", Enciclopedia de Matemáticas , EMS Press
• L-Parser de Laurens Lapré Archivado el 13 de septiembre de 2013 en la Wayback Machine.
• HTML5 L-Systems: pruebe experimentos en línea
• El programa de gráficos vectoriales Inkscape incluye 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 del sistema L y gráficos de tortugas simples en el lenguaje de programación Icon.
• Un generador del sistema Lindenmeyer de Nolan Carroll
• Bloogen: L-Systems con un toque genético

1. Pradal, Christophe; Fournier, cristiano; Valduriez, Patricio; 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) desde el original el 17 de octubre de 2019.
2. Boudon, Federico; Pradal, Christophe; Cokelaer, Thomas; Prusinkiewicz, Przemyslaw; Godín, Christophe (2012). "L-Py: un marco de simulación de sistema L para modelar el desarrollo de arquitectura de plantas basado en un lenguaje dinámico". Fronteras en la ciencia vegetal . 3 : 76. doi : 10.3389/fpls.2012.00076 . PMC 3362793 . PMID  22670147.