Sistema L

Sistema de reescritura y tipo de gramática formal.

Este artículo tiene varios problemas. Ayude a mejorarlo o discuta estos problemas en la página de discusión . ( Obtenga información sobre cómo y cuándo eliminar estos mensajes de plantilla ) Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Buscar fuentes:  "L-system"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( abril de 2013 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla ) Este artículo se lee como un libro de texto y puede requerir una limpieza . Por favor, ayude a mejorar este artículo para que tenga un tono neutro y cumpla con los estándares de calidad de Wikipedia . ( Agosto de 2020 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

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 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 de símbolos más grande, una cadena de " axioma " inicial desde 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 laUniversidad de Utrecht . ^[1] Lindenmayer usó 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 se pueden utilizar para generar fractales auto-similares .

Orígenes

'Weeds', generado 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 diseñaron para proporcionar una descripción formal del desarrollo de organismos multicelulares tan 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 auto-semejanza y, por lo tanto, las formas fractales 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 (consulte la 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 contiene tanto elementos que se pueden reemplazar ( variables ) como aquellos que no se pueden reemplazar ("constantes" o "terminales")
• ω ( inicio , axioma o iniciador ) es una cadena de símbolos de V que definen 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 de identidad A → A; estos símbolos se denominan constantes o terminales . (Ver Ley de identidad ).

Las reglas de la gramática del sistema L se aplican iterativamente 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 solo una regla por iteración. Si las reglas de producción se aplicaran solo una a la vez, simplemente se generaría un lenguaje, en lugar de un sistema L. ^{[ aclaración necesaria ]} Por lo tanto, los sistemas L son subconjuntos estrictos de lenguajes. ^{[ aclaración necesaria ]}

Un sistema L está 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 libres de contexto se especifican por tanto mediante una gramática libre de 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 llama 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 usa 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

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: ABAABABAABAABABAABABA

n = 7: ABAABABAABAABABAABABAABAABABAABAAB

Ejemplo 1: Algas, explicado

n = 0: Un comienzo (axioma / iniciador) / \
n = 1: AB el A inicial único generado en AB por la regla (A → AB), la regla (B → A) no se pudo aplicar / | \
n = 2: ABA anterior cadena AB con todas las reglas aplicadas, A engendró nuevamente en AB, el anterior B se convirtió en A / | | | \
n = 3: ABAAB nota que todas las A están produciendo una copia de sí mismas en primer lugar, luego una B, que gira ... / | | | \ | \ \
n = 4: ABAABABA ... en una A una generación más tarde, comenzando a engendrar / 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 (omitiendo el primer 1, debido a nuestra elección de axioma):

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

Si quisiéramos se salte el primer 1, podemos usar 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 está determinado por si un múltiplo de la proporción áurea cae dentro del intervalo . La proporción de A a B también converge a la media áurea.${\displaystyle (k-1,k)}$

Este ejemplo produce el mismo resultado (en términos de la longitud de cada cadena, no la secuencia de A sy B s) 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.${\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 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:

axioma:	0
1ra recursividad:	1 [0] 0
2da recursividad:	11 [1 [0] 0] 1 [0] 0
3ra recursividad:	1111 [11 [1 [0] 0] 1 [0] 0] 11 [1 [0] 0] 1 [0] 0
...

Podemos ver que esta cuerda crece rápidamente en tamaño y complejidad. Esta cadena se puede dibujar como una imagen usando gráficos de tortugas , 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, la tortuga puede recibir las siguientes instrucciones:

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

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

• Axioma

• Primera recursión

• Segunda recursión

• Tercera recursión

• Cuarta recursividad

• Séptima recursión, reducida diez veces

Ejemplo 3: conjunto Cantor

variables  : AB

constantes  : ninguna

inicio  : una {cadena de caracteres inicial}

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

Supongamos que A significa "avanzar" y B significa "avanzar".

Esto produce el famoso sistema del fractal de Cantor en una recta real R .

Ejemplo 4: curva de Koch

Una variante de la curva de Koch que usa solo á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:

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 + 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 − 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 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 en L de curva de punta de flecha de Sierpiński .

variables  : AB

constantes  : + -

comienzo  : A

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

ángulo  : 60 °

Aquí, A y B significan "avanzar hacia adelante", + 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 con un sistema L.

variables  : FG

constantes  : + -

inicio  : F

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

ángulo  : 90 °

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

Curva de dragón para n = 10

Ejemplo 7: planta fractal

Ver también: helecho de Barnsley

variables  : XF

constantes  : + - []

inicio  : X

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

ángulo  : 25 °

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 de posición y ángulo, que se restauran cuando se ejecuta el correspondiente "]".

Planta fractal para n = 6

Variaciones

Se han desarrollado una serie de elaboraciones sobre esta técnica básica del sistema L que pueden utilizarse conjuntamente. Entre estos se encuentran gramáticas estocásticas , gramáticas sensibles al contexto y gramáticas paramétricas.

Gramáticas estocásticas

El modelo gramatical que hemos discutido hasta ahora ha sido determinista, es decir, dado cualquier símbolo en el alfabeto gramatical, 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 uno una probabilidad de que ocurra. 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 cadenas, habrá un 50% de probabilidad de que se comporte como se describió anteriormente y un 50% de probabilidad de que no cambie durante la producción. Cuando se utiliza una gramática estocástica en un contexto evolutivo , es aconsejable incorporar una semilla aleatoria al genotipo , para 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 mira no solo el símbolo que está modificando, sino también los símbolos en 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 solo si la "a" aparece entre una "b" y una "c" en la cadena de entrada:

… Bac…

Como ocurre 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 con 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 junto con su lista de parámetros se llama 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, 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, un (0,2) se transformaría y un (1,2) no.

En la parte de transformación de la regla de producción, los parámetros y los módulos completos pueden verse afectados. En el ejemplo anterior, el módulo b (x, y) se agrega a la cadena, con los 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,

a (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 un "1" y el parámetro "y" de a se incrementa en uno.

Las gramáticas paramétricas permiten que la gramática determine la longitud de las líneas y los ángulos de ramificación, en lugar de los métodos de interpretación de 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 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 forma. 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 de manera escalonada (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 de diseño y los objetivos se codifican en la traducción en forma de gramática. En aplicaciones de diseño arquitectónico, la gramática bidireccional presenta una conectividad interior consistente y una rica jerarquía espacial. ^[3]

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 solo en el caso en el que solo hay dos variables). ^[4]
• Dada una estructura, encuentre un sistema L que pueda producir esa estructura. ^{[ cita requerida ]}

Tipos de sistemas L

Sistemas L en la línea real R :

• Sistema Prouhet-Thue-Morse

Los sistemas L bien conocidos en un plano R ² son:

• curvas que llenan el espacio ( curva de Hilbert , curvas de Peano , iglesia de Dekking , kolams ),
• curvas medianas que llenan el espacio (curva Lévy C , curva del dragón Harter- Heighway, terdragon Davis-Knuth),
• embaldosados ​​( baldosas esfinge , baldosas Penrose ),
• árboles, plantas y similares.

Ver también

Wikimedia Commons alberga contenido 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 de difusión (incluido el de tipo real)
• Gramática estocástica libre de contexto
• SpeedTree
• La belleza algorítmica de las plantas

Notas

1. Lindenmayer, Aristid (marzo de 1968). "Modelos matemáticos para interacciones celulares en desarrollo II. Filamentos simples y ramificados con entradas de dos caras". Revista de Biología Teórica . 18 (3): 300–315. 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. Hua, H., 2017, diciembre. Un modelo de procedimiento bidireccional para el diseño arquitectónico . En Computer Graphics Forum (Vol. 36, No. 8, págs. 219-231).
4. Kari, Lila; Rozenberg, Grzegorz; Salomaa, Arto (1997). "L Systems". 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 PDF disponible aquí de forma gratuita
• Grzegorz Rozenberg , Arto Salomaa - Lindenmayer Systems: Impactos en la informática teórica, gráficos por computadora y biología del desarrollo ISBN 978-3-540-55320-5 
• DS Ebert, FK Musgrave y col. - Texturizado y modelado: un enfoque procedimental , ISBN 0-12-228730-4 
• Burry, Jane, Burry Mark, (2010). The New Mathematics of Architecture, Nueva York: Thames and Hudson.
• Aristid Lindenmayer, " Modelos matemáticos para la interacción celular en desarrollo ". J. Theoret. Biology, 18: 280-315, 1968.

enlaces externos

• Botánica algorítmica en la Universidad de Calgary
• Ramificación: árbol del sistema L　Un subprograma de Java y su código fuente ( fuente abierta ) de la simulación del crecimiento del árbol botánico utilizando el sistema L.
• Fractint L-System True Fractals
• OpenAlea : un entorno de software de código abierto para el 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 de sistemas L evolutivo (anyos *)
• eXtended L-Systems (XL), gramáticas de crecimiento relacional y plataforma de software de código abierto GroIMP.
• Un subprograma JAVA con muchas figuras fractales generadas por sistemas L. Archivado el 6 de agosto de 2016 en la Wayback Machine.
• My Graphics: una aplicación para iPhone / iPad que genera varios patrones gráficos del sistema L.
• Sistemas L musicales: teoría y aplicaciones sobre el uso de sistemas L para generar estructuras musicales, desde formas de onda hasta macro formas.
• Experimentos en línea con L-Systems usando JSXGraph (JavaScript)
• Implementación de Flea A Ruby de LSYSTEM, utilizando un lenguaje específico de dominio en lugar de comandos del generador concisos
• Lindenmayer power A planta y 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
• Complejidad del sistema L ^{[ enlace muerto ]}
• Una implementación de un analizador de sistema L y gráficos simples de tortugas en el lenguaje de programación Icon
• Un generador de sistema Lindenmeyer de Nolan Carroll
• Bloogen: L-Systems con un toque genético

1. Pradal, Christophe; Fournier, Christian; Valduriez, Patrick; Cohen-Boulakia, Sarah (2015). OpenAlea: flujos de trabajo científicos que combinan análisis y simulación de datos (PDF) . Actas de la 27ª Conferencia Internacional sobre Gestión de Bases de Datos Científicas y Estadísticas - SSDBM '15 . pag. 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: un marco de simulación de L-System para el desarrollo de la arquitectura de la planta de modelado basado en un lenguaje dinámico" . Fronteras en la ciencia de las plantas . 3 : 76. doi : 10.3389 / fpls.2012.00076 . PMC 3362793 . PMID 22670147 .