Teoría de eventos regulares de Kleene y expresiones

En esta sección podremos veremos como es posible representar el comportamiento de un autómata finito por medio de una matriz de transición de estados cuyas entradas son expresiones regulares que definen un lenguaje cada una. A partir de la matriz de transición, podemos conocer que lenguaje aceptará algún autómata dependiendo de su estado inicial y su estado o estados finales, de hecho nosotros podemos indicar cual queremos que sea su estado inicial y su estado o estados finales y así especificar el lenguaje que aceptará dicho autómata. Antes de entrar en detalles, veremos una introducción a la teoría de eventos regulares definida por Stephen Cole Kleene.

Tomemos una máquina $M$ con estado inicial $i$. En la teoría de eventos regulares de Kleene se define $E(i)=\{w\mid o(i_w)=i\}$, como el conjunto de todas las cadenas que lleven a una máquina $M$ de su estado inicial $i$, a estados en los cuales la salida de la misma sea $O(M)=i$. De esta manera el comportamiento de dicha máquina esta caracterizado por los conjuntos $E(i)(i \in O(M))$. Se dice que un conjunto $E$ es representable si, existe una máquina $M$ y una salida $i\in O(M)$ de tal manera que $E(i)=E$, es decir, $E$ esta formado por todas las cadenas que cumplen con la definición de $E(i)$.