Esta entrada pertenece a la serie Teoría de la computación, ¡platicada!
No creo estar muy equivocado si digo que esto de la computación tiene que ver con el tratamiento, manipulación y transformación de la información. A todo esto, ¿qué es la información? ¿Se puede medir? Y, ¿qué significa transformar la información? Para ser capaces de contestar estas preguntas y hacer algo con cualquier clase de información, primero tenemos que representarla de alguna forma. Aquí es donde entran en escena los lenguajes formales.
Los lenguajes y las gramáticas tienen mucho que ver con la teoría de la computación. ¡Sí! ¡De verdad! En realidad tienen todo que ver una con la otra. Sin ellos la computación sería inconcebible.
Claro que no hablamos de los lenguajes de toda la vida, sino de un concepto muy general y abstracto de lo que es un lenguaje. Para los computólogos un lenguaje es, simplemente, un conjunto de cadenas creadas con un cierto conjunto arbitrario de símbolos. A ese conjunto de símbolos se le conoce como alfabeto (faltaba más), y suele representarse con \(\Sigma\).
Aquí tenemos un alfabeto muy simple con dos símbolos:
\(\displaystyle \Sigma = \{a, b\}\)
Un lenguaje muy pequeño con 6 cadenas podría ser algo como:
\(\displaystyle L = \{a, b, aa, bb, aba, baba\}\)
Claro que este lenguaje no es muy interesante, y los que suelen serlo son infinitos. Es decir, aquellos con un número arbitrariamente grande de cadenas. Por ejemplo, un lenguaje que utilizando el alfabeto antes mencionado, incluya a todas las cadenas que empiezan con \(a\) y terminan con \(b\):
\(\displaystyle L = \{ab, aab, abb, aaab, aabb, abab, … \}\)
Puede parecer poca cosa, pero el tratamiento de los lenguajes es una cosa tremendamente poderosa porque, si lo piensas bien, todo lo que es representable de alguna forma, ¡será representado con símbolos! Todo.
Lenguajes especiales
Quiero mencionar lenguajes que por sus particularidades merecen atención especial. Comencemos con la Cerradura de Kleen o Estrella de Kleen. En realidad ésta es una operación que se realiza sobre un conjunto. Su definición es muy simple, y aplicado a un alfabeto, hace alusión al conjunto de todas las cadenas que es posible construir usando dicho alfabeto. Como es obvio, las cadenas pueden ser tan largas como se desee, así que dichos lenguajes son infinitos. Utilizando el alfabeto anterior tendríamos algo como esto:
\(\displaystyle \Sigma^{*} = \{\varepsilon, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, …\}\)
Notar la estrella sobre \(\Sigma\), que hace referencia a la Estrella de Kleen. ¿Y qué es el \(\varepsilon\) que aparece al inicio? Este símbolo especial hace referencia a la cadena vacía, aquella que carece de símbolos. Sí, por muy extraño que suene, una cadena sin símbolos también es una combinación posible de símbolos. Esa combinación donde no hay ninguno.
Como es fácil deducir, si \(\Sigma^*\) posee todas las cadenas posibles que se pueden construir con un alfabeto, entonces, cualquier otro lenguaje que se construya con dicho alfabeto será un subconjunto de \(\Sigma^*\).
Si existe la cadena vacía, ¿por qué no el lenguaje vacío? Aquel que no posee cadena alguna:
\(\displaystyle \emptyset = \{\}\)
¡Cuidado! No es lo mismo el lenguaje vacío que un lenguaje que sólo posea la cadena vacía. ¡La cadena vacía ya es una cadena!
No entiendo de que va esto señor Miyagi
Pero todo esto, ¿qué tiene que ver con la computación, la inteligencia artificial, las máquinas que juegan ajedrez, hablan o la app de mi teléfono? ¡Calma Daniel San! Este es apenas el comienzo, literalmente el alfabeto con el que se escriben los fundamentos de la teoría de la computación. Grandes sorpresas nos esperan delante.
En la siguiente entrada abordaremos las gramáticas, y en particular, las gramáticas regulares.
