Gramáticas De Lindenmayer

Gramáticas de Lindenmayer
Lindenmayer’s grammar

Julián Giraldo Betancur Julián Galvis Escalante
Ingeniería de Sistemas y Computación, Universidad Tecnológica de Pereira, Pereira, Colombia

RESUMEN
Este artículo pretende ofrecer una breve reseña sobre la Gramática de Lindenmayer. Se empieza con un poco de historia para conocer los orígenes de esta teoría, pasando por las diversasdefiniciones de aquellos conceptos necesarios para ampliar el contexto, continuando con el desarrollo de ejemplos del formalismo empleado para tratar la temática y finalmente los diferentes aportes teóricos y prácticos para darle forma al tema y desarrollar un argumento claro. Es importante tener en cuenta que será de mucha utilidad teorías como la del Caos y la de los Fractales para transcender enaplicaciones de los sistemas de Lindenmayer.

PALABRAS CLAVE: Gramáticas, Teoría del Caos, Fractal.

ABSTRACT
This article tries to offer a brief summary about the Lindenmayer grammar. You start with a bit of history to know the origins of this theory, through the various definitions of those concepts necessary to broaden the context, continuing with the development of examples of theformalism used to treat the issue and finally the different theoretical and practical contributions to shape the issue and develop a clear argument. It is important to note that will be useful as theories of Chaos and Fractals to transcend the applications Lindenmayer systems.

KEY WORD: Grammars, Chaos Theory, Fractal.

1. INTRODUCCIÓN

Dentro del isomorfismo de las gramáticas, los lenguajes ylos autómatas, pilares de las ciencias computacionales e informáticas, pretendemos extender la teoría de gramáticas con un caso particular como lo es Los sistemas de Lindenmayer. Quien expande la gramática en un contexto biológico que hace crecer el interés de quienes indagan en estas ciencias. Es a través de la teoría de fractales que nos muestra como las diferentes ciencias pueden estarinterrelacionadas, dando un tratamiento formal y sistémico a los diferentes componentes permitiéndose modelar una técnica de la que se desprenden numerosas aplicaciones.

2. UN POCO DE HISTORIA

Los Sistemas L son un formalismo matemático propuesto por el biólogo Aristid Lindenmayer en 1968 como una base para una teoría axiomática de desarrollo biológico. Éste nuevo tipo de gramáticas fueronllamadas Sistemas de Derivación en Paralelo, o en honor a su creador, Gramáticas de Lindenmayer, Sistemas de Lindenmayer o, más brevemente Sistemas L.

Este tipo de sistemas surgen como un modelo formal del crecimiento de las plantas y sus esfuerzos iniciales se concentraron en la generación automática de imágenes de plantas. A pesar de que estos sistemas se basan en la teoría de lenguajesformales, existen diferencias, por lo que es importante entender que los sistemas Lindenmayer y los lenguajes formales no son lo mismo.

2.1 DFINICIÓN FORMAL DE UN SISTEMA L

Un Sistema L o Gramática de Lindenmayer es la tripla:
(∑, w, P), donde ∑ es el alfabeto de símbolos; w∑*es el axioma o palabra inicial; finalmente, P es un conjunto finito de reglas de producción.

2.2 CLASISFICACIÓNDE LAS GRAMÁTICAS DE LINDENMAYER

Así como las gramáticas de Chomsky se clasifican en cuatro tipos (Gramáticas del tipo 0, 1, 2 y 3), así también entre las Gramáticas de Lindenmayer se distinguen diversos tipos, entre los que se puede mencionar los siguientes:
* Sistemas IL, independientes del contexto: sus reglas tienen la forma xay∷=xvy, donde a ∑ y x,y,v ∑*.
* Sistemas OL, sensiblesal contexto: sus reglas tienen la forma a∷=v, donde a ∑ y v ∑*.
* Sistemas DL, deterministas: para cada símbolo a ∑ sólo puede existir una regla que transforme a en otra cadena, en cada contexto concreto.
Si el Sistema es OL, para cada símbolo sólo puede existir una regla única con dicho símbolo en la parte izquierda.
* Sistemas PL, propagativos: la parte derecha de las reglas no...