Sistema L

El sistema L o sistema Lindenmeier es un sistema de reescritura paralela y un tipo de gramática formal . El sistema L consta de un alfabeto de caracteres que se puede usar para crear cadenas , un conjunto de reglas generativas que especifican reglas de sustitución para cada carácter, una cadena inicial (" axioma ") a partir de la cual comienza la construcción y un mecanismo para traducir la cadena generada en estructuras geométricas. El sistema L fue propuesto y desarrollado en 1968 por Aristide Lindenmeier , un biólogo y botánico húngaro de la Universidad de Utrecht . Lindenmeier usó sistemas L para describir el comportamiento de las células vegetales y modelar el proceso de desarrollo de las plantas . Los sistemas L también se han utilizado para modelar la morfología de varios organismos [1] y se pueden utilizar para generar fractales autosimilares , como sistemas de funciones iteradas .

Orígenes

Como biólogo, Lindenmeier trabajó con levaduras y hongos filamentosos y estudió los patrones de crecimiento de varias especies de algas como el alga azul-verde Anabaena catenula . Inicialmente, los sistemas L se desarrollaron para describir formalmente el desarrollo de estos organismos multicelulares simples y para ilustrar la comunicación entre las células vegetales vecinas. Posteriormente, el 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 se describen fácilmente utilizando el sistema L. Los modelos de plantas y las formas orgánicas de aspecto natural son fáciles de formar, ya que el modelo "crece" lentamente y se vuelve más complejo a medida que aumenta el nivel de recursividad. Los sistemas Lindenmeier también son populares en la generación de vida artificial .

Las gramáticas de los sistemas L son muy similares a los semisistemas de Thue (ver " Jerarquía de Chomsky "). Los sistemas L ahora se conocen como sistemas L paramétricos , que se definen como una tupla

GRAMO = ( V , ω , PAGS ),

dónde

Las reglas gramaticales del sistema L se aplican iterativamente, a partir del axioma (estado inicial). Se aplican tantas reglas como sea posible por iteración. El hecho de que se apliquen tantas reglas como sea posible en cada iteración separa al sistema L de un lenguaje formal generado a partir de una gramática formal que solo aplica una regla por iteración. Si las reglas de inferencia se aplicaran una a la vez, sería fácil generar un lenguaje en lugar de un sistema L. Por lo tanto, los sistemas L son un subconjunto de lenguajes.

Un sistema L no tiene contexto si cada regla de inferencia se refiere solo a caracteres individuales y no a sus vecinos. Los sistemas L independientes del contexto se definen mediante una gramática independiente del contexto . Si la regla depende no solo de un solo símbolo, sino también de los vecinos, el sistema se denomina sistema L sensible al contexto .

Si hay exactamente una regla para cada símbolo, se dice que el sistema L es determinista (un sistema L determinista independiente del contexto se denomina sistema D0L ). Si hay varias reglas, y cada una se elige con alguna probabilidad en cada iteración, entonces este es un sistema L estocástico .

Para usar sistemas L para generar imágenes gráficas, se requiere que los símbolos en el modelo se refieran a los elementos de la imagen en la pantalla de la computadora. Por ejemplo, el programa Fractint usa gráficos de tortugas (similares a los gráficos en el lenguaje Logo ) para producir una imagen en la pantalla. El programa interpreta cada constante en el modelo del sistema L como comandos del sistema de gráficos de tortuga.

Ejemplos de sistemas L

Ejemplo 1: Algas

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

variable  : AB constantes  : no axioma  : A reglas  : (A → AB), (B → A)

El sistema da

n = 0 : A n = 1 : AB n = 2 : ABA n = 3 : ABAAB n = 4 : ABABABA n = 5 : ABAABABAABAAB n = 6 : ABAABABAABAABABAABABABABA n = 7 : ABAABABAABAABABAABAABAABAABABAABAAB Ejemplo 1: Algas, explicación n=0: Un inicio (axioma/iniciador) / \ n=1: AB inicial simple A se convierte en AB por la regla (A → AB), la regla (B → A) no se puede aplicar /| \ n=2: ABA todas las reglas se aplican a la cadena AB, A vuelve a ser AB y B se convierte en A /| | |\ n=3: ABAAB tenga en cuenta que todas las A se traducen en una copia de sí mismas y se agrega B, que se convierte en... /| | |\ |\ \ n=4: ABAABABA ... en A en la próxima generación, resultando en recursividad

El resultado serán palabras de Fibonacci . Si contamos la longitud de cada línea, obtenemos la famosa sucesión de Fibonacci (omitiendo el primer 1):

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

Para cada fila, si contamos la k-ésima posición desde el extremo izquierdo de la fila, el valor depende de si k veces la proporción áurea cae dentro del intervalo . La proporción de ocurrencias de las letras A y B también converge a la proporción áurea.

Este ejemplo da el mismo resultado (en términos de longitud de cadena, no en términos de secuencia de letras A y B ) si la regla ( A → AB ) se reemplaza por ( A → BA ), pero obtenemos cadenas reflejadas.

Esta secuencia es catenante de desde , donde es la n-ésima generación.

Ejemplo 2: El Árbol de Pitágoras

  • variable : 0, 1
  • constantes : [, ]
  • axioma : 0
  • reglas : (1 → 11), (0 → 1[0]0)

La figura se construye aplicando recursivamente las reglas de inferencia al axioma. Cada carácter de la cadena de entrada se compara con la lista de reglas para determinar con qué carácter se debe reemplazar. En este ejemplo, "1" en la entrada se convierte en "11" en la salida, pero "[" no cambia. Aplicando las reglas de inferencia al axioma "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
…

Vemos cadenas que crecen rápidamente en longitud y complejidad. Una cadena se puede dibujar como una imagen utilizando gráficos de tortuga , donde cada carácter tiene una operación gráfica correspondiente para una tortuga. En este ejemplo, se podrían dar los siguientes comandos a la tortuga:

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

"Empujar en la pila" y "salir de la pila" se refieren a la pila LIFO (una gramática más detallada requeriría dividirse en "poner en la pila" y "rotar"). Cuando el intérprete encuentra "[", la posición actual de la tortuga y el ángulo de movimiento se almacenan en la pila; cuando se encuentra "]", la posición y el ángulo se restauran. Si se insertan varios valores en la pila, se restaura el último valor insertado. En la literatura, los sistemas L que utilizan este enfoque de ramificación se denominan "sistemas L entre paréntesis" (sistemas L entre paréntesis) [2] .

Aplicando estas reglas gráficas a la cadena obtenida anteriormente, tenemos:

  • Axioma

  • Primera recursividad

  • Segunda recursividad

  • Tercera recursividad

  • Cuarta recursividad

  • Séptima recursividad, reducida diez veces

Ejemplo 3: conjunto de Cantor

variable : AB constantes : no inicio : A {cadena de inicio} reglas : (A → ABA), (B → BBB)

Deje que A signifique "dibujar una línea" y B signifique "mover".

Tal gramática genera el famoso conjunto fractal de Cantor en el eje real R .

Ejemplo 4: Curva de Koch

Variante de la curva de Koch , utilizando únicamente ángulos rectos.

variable  : F constantes  : + − inicio  : F reglas  : (F → F+F−F−F+F)

Aquí F significa "dibujar una línea", + significa "girar 90° a la izquierda" y − significa "girar 90° a la derecha" (ver " Gráficos de tortugas ").

norte = 0: F n = 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

Triángulo de Sierpinski , dibujado con el sistema L.

variables : FG constantes : + − inicio : F−G−G regla : (F → F−G+F+G−F), (G → GG) ángulo : 120°

Aquí F y G significan "trazar una línea", + significa "girar a la derecha en una esquina" y - significa "girar a la izquierda en una esquina".

  • n=2

  • n=4

  • n=6

También puede aproximar el triángulo de Sierpinski usando el sistema L de curva de flecha de Sierpinski .

variable : AB constantes : + − inicio : A reglas : (A → B−A−B), (B → A+B+A) ángulo : 60°

Aquí A y B significan "dibujar una línea", + significa "girar un ángulo a la izquierda" y − significa "girar un ángulo a la derecha" (ver " Gráficos de tortugas ").

Iteraciones para n =2, n =4, n =6, n =8

Ejemplo 6: Curva de Dragón

Dragon Curve , dibujado con el sistema L.

variable  : XY constantes  : F + − comienzo  : FX reglas  : (X → X+YF+), (Y → −FX−Y) ángulo  : 90°

Aquí F significa "dibujar una línea", − significa "girar 90° a la izquierda" y + significa "girar 90° a la derecha". X e Y no corresponden a ninguna acción de dibujo, sino que solo se utilizan para dibujar una curva.


Iteraciones para n = 10, n = 15

Ejemplo 7: Planta fractal

variable  : XF constantes  : + − [ ] empezar  : X reglas  : (X → F−[[X]+X]+F[+FX]−X), (F → FF) ángulo  : 25°

Aquí F significa "dibujar una línea", − significa "girar 25° a la izquierda" y + significa "girar 25° a la derecha". X no corresponde a ninguna acción de dibujar, solo se usa para dibujar una curva. El corchete "[" corresponde a guardar los valores de posición y ángulo actuales, que se restauran cuando se ejecuta el carácter "]" correspondiente.

Planta fractal para n = 6

Opciones

Se han realizado varios desarrollos basados ​​en la técnica 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

Los modelos gramaticales que acabamos de considerar son deterministas. Es decir, dado cualquier carácter del alfabeto, hay exactamente una regla que siempre se elige y siempre se realiza la misma sustitución. Una alternativa es especificar más de una regla de inferencia para un personaje, dando a cada regla una probabilidad de ejecución. Por ejemplo, en la gramática del ejemplo 2, podemos reemplazar la regla de reescritura "0" con

0 → 1[0]0

en la regla probabilística

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

Con estas reglas de inferencia, cuando se encuentra un "0" en la cadena de entrada, hay un 50 % de posibilidades de que el comportamiento sea el mismo que antes y un 50 % de posibilidades de que nada cambie. Si se utiliza una gramática estocástica en el contexto de la evolución , se recomienda que el generador de aleatoriedad se incorpore al genotipo , para que las propiedades estocásticas del patrón permanezcan constantes entre generaciones.

Gramáticas sensibles al contexto

Una regla de inferencia sensible al contexto analiza no solo los caracteres que modifica, sino también los caracteres que los preceden y los siguen. Por ejemplo, la regla de inferencia:

b < a > c → aa

convierte "a" en "aa", pero solo si "a" está entre "b" y "c" en la cadena de entrada:

…atrás…

Al igual que con la inferencia aleatoria, existen varias reglas para manejar caracteres en diferentes contextos. Si no se encuentra ninguna regla de generación para el contexto especificado, se asume una transformación de identidad y el símbolo no cambia. Si hay reglas de inferencia dependientes e independientes del contexto en la misma gramática, la regla de inferencia sensible al contexto tiene prioridad (si se puede aplicar).

Gramáticas paramétricas

En una gramática paramétrica, cada carácter del alfabeto tiene una lista de parámetros asociada con el carácter. Un símbolo junto con parámetros se denomina módulo, y una cadena en una gramática paramétrica es una secuencia de módulos. Un ejemplo sería la siguiente línea:

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

Los parámetros pueden ser utilizados tanto por la función de dibujo como por las reglas de inferencia. Las reglas de inferencia pueden usar parámetros de dos maneras. En el primer caso, el parámetro se usa en una expresión condicional que determina si se debe aplicar la regla de inferencia. En el segundo caso, la regla de inferencia puede reemplazar los parámetros reales. Por ejemplo, la regla de inferencia:

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

El módulo a(x,y) sufre una transformación de acuerdo con esta regla si se cumple x=0. Por ejemplo, a(0,2) sufrirá una transformación, pero a(1,2) no.

En el lado derecho de la regla de inferencia (en el sucesor), se pueden transformar tanto los parámetros como los módulos completos. En el ejemplo anterior, el módulo b(x,y) se agrega a la cadena con los parámetros iniciales (2,3). Los parámetros de un módulo ya existente se convierten. Con las reglas descritas anteriormente,

un(0,2)

se convierte

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

ya que el parámetro "x" del módulo a(x,y) se convierte explícitamente en "1", y el parámetro "y" se incrementa en uno.

Las gramáticas paramétricas permiten especificar la longitud del segmento y el ángulo de la rama en la gramática, y no en los métodos de interpretación de los gráficos de tortuga. Si la edad también se establece como un parámetro para el módulo, las reglas se pueden cambiar según la edad del segmento de la planta, lo que le permite crear una animación de todo el ciclo de vida del árbol.

Otras categorías de sistemas L

  • Sistemas D0L = sistemas deterministas libres de contexto (ver arriba)
  • Los sistemas L propagativos ("Sistemas L propagativos", "sistemas pL") son sistemas en los que al menos una regla tiene al menos dos letras en el lado derecho (en la salida). Los sistemas no reproductivos tienen un solo símbolo en el lado derecho. La longitud de la palabra en este caso no cambia [3] .
  • Sistemas en L entre paréntesis (consulte el Ejemplo 2)
  • Sistemas 0L, sistemas 1L, sistemas 2L (sistemas IL, también conocidos como sistemas (k,l)) [4] .
  • Los sistemas L tabulares ("sistemas T0L") son sistemas que funcionan con varios conjuntos de reglas. Se utiliza un mecanismo de control externo para seleccionar un conjunto de reglas. Los sistemas L tabulares fueron introducidos y formalizados por Rosenberg en 1975 para modelar la influencia del medio ambiente en el crecimiento de las plantas [5] .

Temas abiertos

Hay muchos problemas abiertos asociados con el estudio de los sistemas L. Por ejemplo:

  • Descripción de todos los L-sistemas deterministas libres de contexto localmente catentativos. (La solución completa sólo se conoce para el caso de tres variables) [6] .
  • Dada una estructura, encuentre un sistema L que pueda reproducir esta estructura.
  • Dados dos sistemas pL y una función de interpolación, ¿serán congruentes los dibujos resultantes [4] ?
  • Dado un sistema pL y una función de interpretación, ¿se cerrará la curva resultante? ¿Será autointersectado o similar a un árbol? ¿Se dibujarán algunos segmentos de línea más de una vez? [4] ?

Las respuestas a estas preguntas son interesantes no solo desde un punto de vista teórico, también son útiles en la construcción de sistemas pL para crear dibujos con propiedades dadas [4] .

Tipos de sistemas L

L-sistemas en el eje real R :

Sistemas L conocidos en el plano R 2 :

Véase también

Notas

  1. ↑ Rozenberg, Salomaa, 1980 .
  2. ↑ Manousakis, 2006 , pág. 26
  3. ↑ Manousakis, 2006 , pág. 28
  4. ↑ 1 2 3 4 Prusinkiewicz, 1986 , p. 252.
  5. ↑ Manousakis, 2006 , pág. 29
  6. ↑ Kari, Rozenberg, Salomaa, 1997 , pág. 262.

Literatura

  • Grzegorz Rozenberg, Arto Salomaa. La teoría matemática de los sistemas L. - Nueva York: Academic Press, 1980. - ISBN 0-12-597140-0 .
  • Przemysław Prusinkiewicz, Aristid Lindenmayer . La belleza algorítmica de las plantas. — Springer, 2004.
  • Grzegorz Rozenberg, Arto Salomaa. Sistemas Lindenmayer: impactos en la informática teórica, los gráficos por computadora y la biología del desarrollo. - Springer-Verlag, 1992. - ISBN 978-3-540-55320-5 .
  • DS Ebert, FK Musgrave, D. Peachey, K. Perlin. Texturizado y modelado: un enfoque procedimental. - Prensa académica, 1994. - ISBN 0-12-228730-4 .
  • Burry, Jane, Burry Mark. Las Nuevas Matemáticas de la Arquitectura. — Nueva York: Thames and Hudson, 2010.
  • Aristide Lindenmayer. Modelos matemáticos para la interacción celular en el desarrollo // J. Theoret. Biología. - 1968. - Emisión. 18 _ - S. 280-315 .
  • P. prusinkiewicz. Actas de Graphics Interface '86 / Vision Interface '86. - 1986. - S. 247−253 ..
  • Manual de lenguajes formales / G.Rozenberg, A.Salomaa. - Springer, 1997. - V. 1 (Palabra, Lenguaje, Gramática). - S. 253-328. - ISBN 978-3-642-63863-3 .
  • Stelios Manousakis. Sistemas L musicales. - La Haya: The Royal Conservatory, 2006. - (Tesis de Maestría - Sonología).

Enlaces