Katherine Molina
Autómatas y Lenguajes Formales
Crecer en paralelo
¿Qué le pasa a una gramática si, en vez de reescribir un símbolo por vez, reescribe todos a la vez?
Las plantas crecen así: todas sus células se dividen al mismo tiempo. En 1968, Aristid Lindenmayer convirtió esa observación en un formalismo. Este sitio usa ese formalismo para recorrer la teoría de la materia, de los alfabetos a la jerarquía de Chomsky.
Un biólogo mirando cómo crecen las células
Lindenmayer no era informático: estudiaba el desarrollo de organismos simples, como levaduras, hongos y algas. Observó que en un tejido vivo todas las células se dividen al mismo tiempo, y en 1968 propuso describir ese crecimiento con reglas de reescritura que se aplican a todos los símbolos a la vez.
- Nació
- Budapest, Hungría, 1925
- Estudió
- Química y biología en Budapest · Doctorado en fisiología vegetal, Universidad de Michigan (1956)
- Trabajó
- Universidad de Utrecht, Países Bajos, desde 1968
- Publicó
- Mathematical models for cellular interaction in development (1968)
Su alga de 1968: a → ab · b → a
Una célula madura a se divide en a y b; una célula joven b madura y pasa a ser a. Todas a la vez.
De las células a los dibujos
En los años 80, Przemysław Prusinkiewicz propuso leer las cadenas de un L-system como instrucciones para una tortuga que dibuja: avanzar, girar, abrir y cerrar ramas. Así el formalismo de Lindenmayer pasó a generar imágenes de plantas.
- Trabaja
- Profesor de Ciencias de la Computación, Universidad de Calgary, Canadá
- Escribió
- Con Lindenmayer, The Algorithmic Beauty of Plants (Springer, 1990), el libro de referencia sobre el tema
- Premio
- SIGGRAPH Computer Graphics Achievement Award (1997)
Una planta es una palabra
Un L-system es una terna G = (Σ, P, ω): un alfabeto, un conjunto de producciones y un axioma. En cada paso, todos los símbolos de la cadena se reemplazan a la vez. La planta que ves es solo una forma de leer esa cadena.
El sistema
- F avanza y dibuja un tramo de tallo
- X es un brote: no dibuja, pero va a crecer
- + − giran a la izquierda o a la derecha
- [ ] abren y cierran una rama
La derivación, paso a paso
Uno por vez, o todos a la vez
La misma regla, F → FF, con el mismo axioma F. Lo único que cambia es cómo se aplica. Apretá “Siguiente paso” y mirá cómo se separan los dos mundos.
Secuencial (Chomsky)
una ocurrencia por pasoParalelo (Lindenmayer)
todas a la vezLargo de la cadena en cada paso
Los dos lenguajes
| Modo | Lenguaje | Clase |
|---|---|---|
| Secuencial | { Fⁿ : n ≥ 1 }expresión regular: FF* | Regular |
| Paralelo | { F2ⁿ : n ≥ 0 }1, 2, 4, 8, 16… símbolos | Ni regular ni libre de contexto |
Para comparar en igualdad de condiciones, en los dos modos el lenguaje es el conjunto de todas las cadenas derivadas desde el axioma.
El modo secuencial, escrito como gramática regular
Aplicar F → FF de a una ocurrencia genera exactamente las mismas palabras que esta gramática. Así se escribe con las reglas de la materia:
- N
{ S }· no terminales: símbolos auxiliares que todavía hay que reemplazar.- T
{ F }· terminales: los símbolos con los que se escribe la palabra final.- P
S → F SyS → F· producciones. Tienen la formaA → aBoA → a(lineal a derecha): por eso la gramática es regular.- S
- Símbolo distinguido o axioma: a partir de él se empieza a generar.
Probá derivar una palabra, un paso por vez:
La diferencia: gramática regular frente a L-system
| Gramática regular (Chomsky) | L-system | |
|---|---|---|
| Símbolos | Separados: no terminales (S) y terminales (F) | Un solo alfabeto: la misma F se reescribe |
| Cada paso | Reemplaza una ocurrencia de un no terminal | Reemplaza todos los símbolos a la vez |
| Qué es una palabra del lenguaje | Solo cuando no queda ningún no terminal (sin S) | Toda palabra derivada, desde el axioma |
Lo que un autómata finito no puede
¿Cómo sabemos que { F2ⁿ } no es regular?
El juego
-
Supongamos que un AFD con p estados reconoce el lenguaje.
-
Vos partís
w = xyz, con|xy| ≤ py|y| ≥ 1: -
Bombeamos
y: repetimosiveces.
¿De dónde sale la y?
El autómata que supusimos, con la partición que se eligió:
Cómo lee el autómata x yi z
¿Por qué existe el bucle? Con p estados, al leer p símbolos el autómata pasa por p + 1 estados: por el principio del palomar repite uno (q). Lo que lee entre las dos visitas a q es la y, y puede recorrerla 0, 1, 2… veces sin darse cuenta.
Qué pasa
w original
x yi z
La tortuga necesita una pila
Para dibujar, una “tortuga” lee la cadena símbolo por símbolo. Cuando entra a una rama ([) tiene que acordarse de dónde estaba, y cuando sale (]) tiene que volver ahí. Guardar y recuperar en orden inverso es exactamente una pila.
Apretá reproducir para que la tortuga empiece a leer.
Pila
profundidad 0 · máxima 0El intérprete como autómata de pila
En rigor la pila guarda datos numéricos (posición y ángulo), así que el intérprete es un transductor de pila: un autómata de pila que además produce una salida, el dibujo. La parte que decide si la cadena está bien formada es el autómata de pila clásico sobre el lenguaje de corchetes balanceados (Dyck).
¿Y si no tuviera pila?
En la iteración n la planta tiene ramas anidadas a profundidad n. Las cadenas [, [[, [[[… son distinguibles entre sí: después de cada una hacen falta cantidades distintas de ]. Un AFD con k estados solo puede distinguir k de ellas, así que a partir de la profundidad k + 1 se pierde.
El mapa: los L-systems cruzan la jerarquía
Los L-systems no son un escalón más arriba ni más abajo. Su clase corta a los regulares y a los libres de contexto sin contenerlos, y todo queda adentro de los sensibles al contexto. Tocá cada punto o cada región.
Matemática que crece
En un L-system determinístico, cuántos símbolos de cada tipo hay en el paso n + 1 depende linealmente de cuántos había en el paso n. Eso conecta los lenguajes formales con sucesiones, matrices, autovalores y logaritmos.
El alga de Lindenmayer (1968)
Cada a produce una a y una b; cada b produce una a. Por eso el vector (#a, #b) se multiplica por M en cada paso, y Mⁿ tiene números de Fibonacci adentro.
La cadena y sus cuentas
El cociente entre largos consecutivos tiende al número áureo
λ² − λ − 1 = 0 ⇒ λ = (1 + √5) / 2 ≈ 1,6180
El autovalor dominante de M es φ. Por eso el largo crece aproximadamente como φⁿ: la velocidad de crecimiento de la planta es un autovalor.
Curvas que se repiten a sí mismas
Dimensión fractal
Si una figura está formada por N copias de sí misma, cada una achicada por un factor s, su dimensión es
D = log N / log (1/s)
Una recta: 2 copias a la mitad → D = 1. Un cuadrado: 4 copias a la mitad → D = 2. La curva de Koch: 4 copias a un tercio → D ≈ 1,26. Es “más que una línea y menos que una superficie”. El largo de la curva se multiplica por 4/3 en cada paso, así que tiende a infinito dentro de una región acotada.
Largo de la cadena según n (escala logarítmica)
Los autovalores deciden
| Sistema | Matriz | Largo |
|---|---|---|
F → FF | [2] | 2ⁿ · exponencial |
a → ab, b → a | [[1,1],[1,0]] | ≈ φⁿ · exponencial |
a → ab, b → b | [[1,0],[1,1]] | n + 1 · lineal |
Si el mayor autovalor es mayor que 1, el crecimiento es exponencial. Si es 1, es polinomial. Una propiedad del lenguaje (cómo crecen sus palabras) se lee en una matriz.
Probá tus propios sistemas
Elegí un ejemplo o escribí tus reglas. El laboratorio deriva en paralelo, valida los corchetes con un autómata de pila y dibuja el resultado.