Esta entrada pertenece a la serie Teoría de la computación, ¡platicada!
Como ya vimos en la entrada anterior, un lenguaje es un conjunto arbitrario de cadenas de símbolos, los cuales se eligen de un alfabeto. Si no la has leído, te recomiendo encarecidamente que lo hagas, de lo contrario tal vez entiendas poco de ésta.
Muy bien, ya sabemos qué es un lenguaje. Ahora, ¿cómo se construyen? Hay dos formas de conseguirlo: la primera es listando las cadenas que lo constituyen de forma explícita, la segunda es estableciendo un procedimiento que genere las cadenas de nuestro lenguaje. A los procedimientos que generan, y por tanto definen a un lenguaje, los llamamos gramáticas.
Si nuestro lenguaje es infinito, ya nos podemos quedar a esperar la muerte de nuestro universo antes de listar todas las cadenas que lo constituyen, ¡porque no acabaríamos nunca! En ese caso será mucho mejor establecer las pautas que las generan, es decir, establecer una gramática. Aquí entran en escena los autómatas.
Tal vez cuando te dicen «autómata» pienses en algo como ésto:
Pero no vayas tan lejos, aquí nos referimos más bien a ésto otro:
Autómatas finitos
Los autómatas finitos son máquinas de estados. ¿Qué es eso? Son sistemas que constan de varias partes: de entrada tienen un conjunto de estados (por supuesto, por eso se llaman máquinas de estados) que solemos llamar \(Q\). También poseen un conjunto de reglas de transición que nos dicen cómo pasar de un estado a otro, a ese lo solemos llamar \(\delta\). Tienen un estado inicial, un primer estado, que solemos llamar \(q_{0}\) y que pertenece a \(Q\). Dicho formalmente: \(q_{0} \in Q\). Poseen un alfabeto \(\Sigma\) de los que ya conocemos. Por último, poseen un conjunto de estados finales o de aceptación que solemos llamar \(F\) y que también forma parte de \(Q\). Es decir: \(F \subset Q\).
Es decir, un autómata finito es una tupla de todas esas cosas:
\(\displaystyle A = (Q, \Sigma, \delta, q_{0}, F)\)
¿Y cómo diablos «eso» genera un lenguaje? Vayamos por partes. Regresemos al autómata anterior:
Los estados son representados con los círculos. El estado inicial \(q_{0}\) se encuentra a la izquierda. Cada flecha corresponde a una transición, el viaje de un estado a otro. Cada transición está marcada con un símbolo del alfabeto. Es el símbolo que nos hace viajar de un estado a otro. Los estados finales está representados como círculos dobles.
Los autómatas generan cadenas de un lenguaje haciendo un viaje desde el nodo inicial a uno de los nodos finales. Al inicio tendremos una cadena vacía. Durante el recorrido será inevitable recorrer algunas flechas. Cada que pasemos por una de ellas se agregará a la cadena el símbolo asociado (sólo uno de ellos si hay más de uno).
Cuando estemos «parados» en un estado final tendremos una cadena compuesta de diversos símbolos. ¡Felicidades! Tenemos una cadena del lenguaje. Como es fácil intuir, según sea el arreglo de estados y transiciones, se podrán crear algunas cadenas y otras no.
Decimos que un autómata acepta una cadena, si dicha cadena al ser introducida en el autómata nos conduce a un estado final. En caso contrario, no es aceptada y no forma parte del lenguaje.
A los lenguajes que pueden ser descritos de esta forma se les llama lenguajes regulares, y a las gramáticas que los generan gramáticas regulares.
¿Se pueden crear todos los lenguajes imaginables con un autómata finito? La respuesta corta es NO. Los lenguajes son una colección arbitraria de cadenas, pero no todas las colecciones se pueden definir con un autómata. No está de más aclarar que nos referimos a colecciones infinitas de cadenas. Toda colección finita puede ser descrita con un autómata finito.
Expresiones regulares
Dibujar un autómata puede ser una tarea engorrosa y utilizar mucho espacio. Una manera más práctica de representar y hacer alusión a un lenguaje regular es utilizando una expresión regular.
Una expresión regular sintetiza las reglas que definen la creación de cada una de las cadenas de un lenguaje regular. Se puede demostrar que todo autómata finito como los descritos arriba puede ser expresado como una expresión regular y viceversa.
Consiste en una cadena con elementos del alfabeto y otros más que indican la forma en que ellos pueden ser plasmados en la cadena final. Se pueden utilizar los siguientes símbolos.
- \(a\). Una expresión regular. La más simple consta de un símbolo del alfabeto.
- \(ab\). Sí \(a\) y \(b\) son expresiones regulares, \(ab\) es su concatenación.
- \(+\). Un operador lógico OR.
- \(*\) (superíndice). La cerradura de Kleen. Equivale a repetir un número arbitrario de veces la expresión regular afectada.
Las expresiones regulares se pueden agrupar con paréntesis de forma que los operadores afecten a su interior como una sola unidad y no a símbolos individuales, como cabría esperar.
Para el autómata finito presentado en esta entrada, una expresión regular que lo representa podría ser esta:
\(\displaystyle L = a(aa)^{*} + b + a(aa)^{*}bb(bb)^{*}\)
No todo es regular
Imagínese el lenguaje que está compuesto por todas las cadenas que inician con una secuencia de símbolos \(a\) y que terminan con la misma cantidad de símbolos \(b\). Algo así:
\(\displaystyle L = \{\varepsilon, ab, aabb, aaabbb, aaaabbbb, aaaaabbbbb, …\}\)
Con el tiempo suficiente será evidente que no se puede construir un autómata que realice dicha labor. Para ser capaces de ella necesitamos ampliar nuestro repertorio gramatical.
En la siguiente entrega abordaremos las gramáticas libres de contexto, que nos permitirán definir un lenguaje como el mencionado arriba.
