Autómata Finito

Recordando lo visto en la sección 2.4, una expresión regular es una forma de describir un lenguaje, pero, ¿Cómo haríamos para saber si una cadena pertenece o no al lenguaje?
Una forma de hacerlo es construyendo un diagrama que contenga la información necesaria para analizar la cadena, este diagrama tendrá forma de grafo dirigido¹. La cadena será leída de izquierda a derecha.
Para dar a conocer que la cadena es aceptada, se debe establecer un estado de aceptación y también se deben establecer estados de no aceptación para terminar el análisis de las cadenas que no pertenescan al lenguaje. Los estados, tanto de aceptación como los que no lo son, serán representados por medio de nodos en el grafo, los cuales es conveniente etiquetar de alguna forma, así que definiremos $Q=\{q_1,q_2,\ldots,q_n\}$ como el conjunto finito de todos los estados posibles, $q_1$ será el estado inicial y $F\subseteq Q$ será el conjunto finito de todos los estados finales, es decir, estados de aceptación.
Tomaremos a la cadena que será analizada como nuestro alfabeto de entrada y lo denotaremos como $\Sigma$. Cada arista en el grafo es etiquetada con un símbolo de $\Sigma$ que indica una transición de algún estado a otro en el sentido marcado por la flecha en algúno de los extremos de cada arista. Al analizar un carácter es posible permanecer en el mismo estado después de la transición. Los estados de aceptación deben de distinguirse de los demás, por lo que serán encerrados en un círculo.
Analizar una cadena es recorrer los caminos del grafo; dependiendo del carácter que esta siendo análizado se elige un camino a recorrer. Cuando se acepta una cadena como miembro del lenguaje se llega a un estado de aceptación (encerrados en un círculo) por lo que, todos los caminos que lleven a un estado de aceptación construyen palabras pertenecientes a el lenguaje.
Ejemplo: Si tenemos, el alfabeto $\Sigma=\{a,b\}$ y el lenguaje descrito por la expresión regular $(ab)^*=\{\varepsilon,ab,(ab)^2\ldots,(ab)^n\}$, para demostrar que la cadena $c=ab$ pertenece a este lenguaje construimos el diagrama de la figura 1.

Figura 1: Gráfo para analizar el lenguaje descrito por la expresión regular $(ab)^*$

También se puede describir la forma en que la cadena es procesada por medio de un tabla, la cual contiene la información acerca de las transiciones que se realizan al recorrer la cadena. En dicha tabla tendremos relacionadas parejas de la forma $(q_i,\alpha)$, donde $q_i\in S$ , $i=(1,2,\ldots)$ y $\alpha$ es un carácter de la cadena que se esta analizando. A partir de un estado y un carácter podremos decir cual será el camino que debe ser recorrido en el grafo, el cual nos llevará hacía algún estado en $Q$, por lo que podemos definir una función $\delta(q_i,\alpha)$, que depende de dos variables, el estado actual y el carácter analizado, en otras palabras la función tomará pares de la forma $Q\times \Sigma$, para definir a que estado se llegará, entonces podemos definir más generalmene la función de transición de estados como sigue:
Sean $Q$ el conjunto de todos los estados, $\Sigma$ un alfabeto de entrada y $\alpha$ un carácter que pertenece a $\Sigma$ y $\delta$ una función o regla de transformación, entonces $\delta$ es de la forma $\delta:Q\times\Sigma \rightarrow Q$. La tabla 1 describe como es analizada la cadena $ab$ con el diagrama de la figura 1.

Tabla 1: Tabla de transición de estados del diagrama de la figura 1.

$\delta$	$a$	$b$
$q_1$	$q_2$	$\times$
$q_2$	$q_1$	$\times$

Se puede apreciar que al analizar la cadena $ab$, primero se pasa de $q_1$ a $q_2$ por medio de la arista $a$ en el sentido indicado por la flecha, después cuando se analiza $b$ se pasa de $q_2$ a $q_1$, por medio de la arista $b$, la cadena a sido analizada por completo y $q_1$ es un estado de aceptación, por lo que la cadena es aceptada como parte del lenguaje descrito por $(ab)^*$. Si tratamos de analizar otra cadena como $aaa$, podemos ver que no hay una transición definida para cuando uno está en el estado $q_2$ y se analiza una $a$, por lo que se permanece en este estado. El cual no es un estado de aceptación y la cadena nunca termina de ser analizada, por lo que estamos seguros que $aaa$ no pertenece a el lenguaje descrito por la expresión regular $(ab)^*$.
Supongamos que existe una máquina imaginaria que puede realizar la tarea de analizar cadenas y decir si éstas pertenecen a cierto lenguaje o no. Este tipo de máquinas son conocidas como máquinas de estados finitos o autómata finito(AF). El cual se define formalmente como una 5-tupla, $M=(Q,\Sigma,F,s,\delta)$ donde:

• $\Sigma$, es algún alfabeto de entrada.
• $S$, es el conjunto finito de todos los estados.
• $F\subseteq S$, es el conjunto de estados finales o de aceptación.
• $s_1\in S$, es el estado inicial de la máquina(AF)
• $\delta$, es la función de transición de estados $\delta:S\times \alpha \rightarrow S.$

Existen varios tipo de autómatas, algunos de ellos serán brevemente descritos en la sección 2.6.2, indicando que tipo de lenguaje es capaz de reconocer cada uno. Así como hay diferentes tipos de autómata, existen diferentes tipos de lenguajes y cada uno de estos lenguajes pueden ser reconocidos por algún tipo de autómata.
Las diferencias entre los lenguajes radican en la forma en la que se estructuran, ésta estructura es definida por algún tipo de gramática, este concepto se analizará en la siguiente sección de una manera breve.