Siguiente: Expresiones regulares y sistemas
Un nivel arriba: Expresiones regulares
Anterior: Matrices de expresiones regulares
Veremos en esta sección que se cumple el recíproco de la proposición 4.2.3: Todo lenguaje regular ha de ser formalmente regular.
Sea
una gráfica de transición. Consideremos la siguiente transformación:
Observación 4.1
El lenguaje de la gráfica de transición
coincide con el conjunto
.
Por tanto, se tiene la igualdad conjuntista
donde
.
Y puesta la igualdad anterior como una expresión regular queda
|
(39) |
Ahora, de manera similar a como se hizo en la ec. (3.6), definimos la relación de indistinguibilidad entre los estados de GT haciendo
|
(40) |
y de hecho la extendemos al conjunto de subconjuntos de estados,
,
haciendo
|
(41) |
Y, también a como se hizo en el caso de los autómatas finitos, se tiene inducida una relación de indistinguibilidad en el diccionario de entrada:
|
(42) |
donde
.
Ahora bien, se tiene una correspondencia entre la imagen de ,
o sea el conjunto de estados de
,
y las partes de Q que son accesibles desde el estado inicial q0 en la gráfica.
Por tanto, podemos calcular al autómata cociente
de manera similar a como se calcula el autómata equivalente a una gráfica de transición. En la Figura 4.1 presentamos el seudocódigo de este procedimiento.
Si
es el conjunto de estados de la gráfica, la lista
denota al subconjunto Q' tal que para todo j,
.
Figure:
Cálculo de la imagen de
para una gráfica de transición dada.
|
Habiendo calculado
,
supongamos que
donde
corresponde a la palabra vacía.
En este caso, las ecuaciones 4.28 dan un sistema de
ecuaciones con
``incógnitas''
de la forma
|
(43) |
donde
es la suma de símbolos que en
hacen transitar a
hacia :
y
Puesto de manera matricial, el sistema de ecuaciones 4.32 queda de la forma
y por la manera en la que se construyó, la matriz
no posee la CPV, por tanto
En la primera entrada de este vector, es decir, la correspondiente a ,
se obtiene una expresión regular que describe al lenguaje reconocido por la gráfica de transición.
En resumen, se tiene la
Proposición 4.1 (Kleene)
El lenguaje reconocido por cualquier gráfica de transición se puede expresar mediante una expresión regular. Es decir, todo lenguaje regular es formalmente regular.
Así pues, para una gráfica de transición
con sólo dos estados q1 y q2. Hagamos
Entonces, de la ec. (4.27) obtenemos:
Ejemplo:
Sea
la gráfica de transición vista anteriormente, donde
,
,
q0=0,
y las transiciones son
.
Al aplicar el algoritmo 4.1 obtenemos la tabla siguiente:
Por tanto,
y se obtiene el sistema de ecuaciones
Puesto de manera matricial el anterior sistema de ecuaciones queda de la forma
El lenguaje de la gráfica de transición quedará expresado por
donde
Al calcular la operación ``estrella'', se obtiene
y consecuentemente, el lenguaje reconocido por la gráfica de transición es
Así pues, para una gráfica de transición
con sólo dos estados q1 y q2. Hagamos
Entonces, de la ec. (4.27) obtenemos:
Ejemplo:
Sea
la gráfica de transición vista anteriormente, donde
,
,
q0=0,
y las transiciones son
.
Al aplicar el algoritmo 4.1 obtenemos la tabla siguiente:
Por tanto,
y se obtiene el sistema de ecuaciones
Puesto de manera matricial el anterior sistema de ecuaciones queda de la forma
El lenguaje de la gráfica de transición quedará expresado por
donde
Al calcular la operación ``estrella'', se obtiene
y consecuentemente, el lenguaje reconocido por la gráfica de transición es
Siguiente: Expresiones regulares y sistemas
Un nivel arriba: Expresiones regulares
Anterior: Matrices de expresiones regulares
Guillermo Morales-Luna
2000-06-27