Gramáticas

Últimamente he pensado muchas cosas para escribir aquí, pero todas son ofensivas y -como ya he dicho antes- no quiero que esta madre se vuelva de esas de "el mundo apesta y todos son unos idiotas".

Así que veamos algo interesante: las gramáticas.

Primero hay que aclarar que no me refiero a la gramática del español. Sin embargo, lo que vamos a ver es similar a ella.

Una gramática no es más que una descripción de un lenguaje formal. Un lenguaje formal no es otra cosa que un conjunto de cadenas. Aunque estoy ya me está saliendo mal, porque quizá no saben a qué me refiero con cadenas.

Los que hayan llevado algo de programación y eso saben que a los arreglos de letras se les llaman 'cadenas'. Pero si no han llevado nada de esas cosas ¡no se preocupen! Les voy a llamar mejor 'palabras' (todos saben qué es eso ¿no?)

Entonces volvamos a empezar desde el mero principio para que me entiendan (en serio, es bieeeen fácil ¡no se preocupen!)

Primero tenemos algo a lo que le vamos a decir alfabeto, que no es otra cosa que un conjunto finito. Por ejemplo, el alfabeto que conocemos cumple esta descripción, pero también el conjunto {0,1} es un alfabeto. {a,b,c} es otro ejemplo de un alfabeto.

Una palabra sobre un alfabeto dado, entonces, no es más que un montón de símbolos (les pueden decir letras... nomás que los números a veces pueden ser letras y se hace una bronca, pero si le entienden no hay tos) de nuestro alfabeto pegados.

Volviendo a nuestro ejemplo del alfabeto normal, 'tengohueva' es una palabra, pero 'tengo hueva' no lo es porque el ' ' no es un símbolo de ese alfabeto (aunque se lo pueden pegar y hacer un nuevo alfabeto y no hay problema).

Otro ejemplo: sobre el alfabeto {0,1}, '000111' es una palabra, pero '00200' no lo es (sobre ese mismo alfabeto, claro). Pueden construir sus propios alfabetos y cosas así ¡es divertido! (ja).

Como dato así mamonsón, el conjunto de todas las posibles palabras sobre un alfabeto S se llama la "cerradura de Kleene" de S.

Entonces ya estamos en qué es una palabra ¿Dónde entran las gramáticas?

Tranquiiilos. Primero vamos a ver qué es un lenguaje formal: un lenguaje formal es simplemente un conjunto de palabras que se pueden formar con los símbolos de un alfabeto.

Y ése, mis estimados, es el punto fino.

¿Si tienen un conjunto de palabras, cómo podrían dar "reglas" para formar todas, sin tener que describirlas una por una?

Por ejemplo, si les digo que sobre el alfabeto {0,1} el lenguaje {0,1,00,11,000,111,...} ¿cómo le harían para describir ese conjunto sin tener que describirlo poniendo tooooodas las palabras? ¿Qué tal si son infinitas?

Una manera de describir ciertos tipos de lenguajes es con autómatas finitos. Pero pues eso es un poco más largo de contar y la verdad ya me está dando hueva... así que sigamos rápidamente con las gramáticas.

Una gramática (generadora) es una colección de "reglas de producción" que permiten ser sustituidos una y otra y otra y las veces que uno quiera antes de llegar a un "símbolo terminal" (o sea que cuando lo ponemos ya no podemos sustituirlo).

Esto de las reglas de producción está medio macabro, pero lo explico con ejemplos porque pues nos vamos a aburrir si comienzo con la cerradura de Kleene de la unión del conjunto de símbolos terminales con los no terminales y eso. Al que le interese le cuento bien.

Entonces, por ejemplo, para generar a ese lenguaje que puse arriba ({0,1,00,11,000,111,...}), las reglas de producción irían como sigue:

1. S -> 0A | 1B
2. A -> 0A | #
3. B -> 1B | #

Que en cristiano se lee así: "el símbolo inicial S puede sustituirse por 0A o 1B, A puede sustituirse por 0A o # (# es el símbolo vacío... nomás sirve para que pare el proceso, no aparece nada en la cadena), y B puede sustituirse por 1B".

Para que quede aún más claro, pongo un ejemplo: Supongamos que queremos generar la cadena '00000'. Entonces lo único que debo hacer es

- Empezar con el S y sustituirlo por 0A. Se ve así: S->0A.
- De ahí el A sustituirlo otra vez por 0A. 0A -> 00A.
- Otra vez sustituir A por 0A. 00A -> 000A.
- Otra vez. Cuatro ceros. 000A -> 0000A.
- Otra vez. Cinco ceros. 0000A -> 00000A.
- Ahora no debo sustituir el A por 0A (eso haría que tuviera seis ceros). Para eso tengo mi símbolo eso que me detiene la máquina y que, de pilón, no aparece en la palabra. Entonces tengo:

00000A -> 00000

Que es la palabra a la que queríamos llegar. Ooooohhhh.

¿Y para qué sirve esta basura, Aldo? Preguntarán ustedes.

Pues... entre otras cosas para el fundamento teórico del funcionamiento del software de computadoras, para teoría de grupos, fractales. Hay un montón de cosas que uno puede aprender con estas madres.

De hecho uno puede hacer dibujitos con gramáticas, usando un programa que hizo mi profe de Arquitectura de una Computadora (seguramente lo que se imaginaron NO es lo que vemos en mi materia) que hace curvas recursivas. Está aquí.

Ahí está su manual de uso, así que no comiencen con que "komo funsiona omglollzzzz?!".

Por ejemplo, si le ponen en el cuadrito:

axiom
A(90)
S(3)
y;

rules 1
y= zFzFzFzF;
end


rules 7
z=F S(S*(1/2)) -F-F-FzFzFzF+ ++f-- S(S*(2));
z=F-;
end


Les va a aparecer



Bueno. Si les interesa qué chido. Si no, al menos ya me relajé un rato y conté algo de provecho.