áles estados son k-equivalentes. Específicamente, si s y t son estados (k ฀ 1)-equivalentes cuyos estados-próximos son (k ฀ 1)-equivalentes para cu...

áles estados son k-equivalentes. Específicamente, si s y t son estados (k ฀ 1)-equivalentes cuyos estados-próximos son (k ฀ 1)-equivalentes para cualquier símbolo de entrada m, entonces s y t son k-equivalentes. Así, las clases de k-equivalencia son las que obtienes subdividiendo las clases de (k ฀ 1)-equivalencia de acuerdo a la acción de la función de siguiente estado sobre los miembros de las clases. Un ejemplo debería hacer claro este procedimiento. Ejemplo 12.3.2 Determinación de clases de k-equivalencia Encuentre las clases de 0-equivalencia, las clases de 1-equivalencia y las clases de 2-equi-valencia para los estados del autómata que se muestra a continuación. 0 11 1 1 0 0 0 1 s2 s3 s1s0 s4 Solución 1. Clases de 0-equivalencia: Por el teorema 12.3.1 dos estados son 0-equivalentes si y sólo si, ambos son estados aceptables o los dos son estados no-aceptables. Así que existen dos conjuntos de estados 0-equivalentes: {s0, s1, s4}(los estados no-aceptables) y {s2, s3}(los estados aceptables), y así las clases de 0-equivalencia son {s0, s1, s4} y {s2, s3}. 2. Clases de 1-equivalencia: Por el teorema 12.3.1, dos estados son 1-equivalentes si y sólo si, ellos son 0-equivalentes y, después de introducir cualquier símbolo de entrada, sus próximos estados son 0-equivalentes. Así s1 no es 1-equivalente a s0 porque cuando un 0 entra al autómata en el estado s1, éste va al estado s2, mientras que cuando un 0 entra al autómata en el estado s0, éste va al estado s0, pero s2 y s0 no son 0-equivalentes. Por otro lado, s1 es 1-equivalente a s4 porque cuando un 0 entra al autómata en el estado s1 o s4 los estados-próximos son s2 y s3, los cuales son 0-equivalentes; y cuando un 1 entra al autómata en el estado s1 o s4 los estados siguientes son s4 y s1, los cuales son 0-equivalentes. Por un argumento similar, s2 es 1-equivalente a s3. Como los estados 1-equivalentes también deben ser 0-equivalentes [por la propiedad (12.3.4)], entonces no existen otros pares de estados que sean 1-equivalentes. Por lo tanto, las clases de 1-equivalencia son {s0},{s1, s4} y {s2, s3}. 3. Clases de 2-equivalencia: Por el teorema 12.3.1, dos estados son 2-equivalentes si y sólo si, ellos son 1-equivalentes y, después de introducir cualquier símbolo de entrada, sus estados-próximos son 1-equivalentes. Ahora s1 es 2-equivalente a s4 porque ellos son 1-equivalentes y cuando un 1 entra al autómata en el estado s1 o s4 los estados-próximos son s4 y s1, los cuales son 1-equivalentes; y cuando un 0 entra al autómata en el estado s1 o s4 los estados próximos son s2 y s3, los cuales son 1-equivalentes. Similarmente, s2 es 2-equivalente a s3. Pero estados 2-equivalentes también deben ser 1-equivalen- tes [por la propiedad (12.3.4)], no existen otros pares de estados que sean 2-equivalentes. Así las clases de 2-equivalencia son {s0}, {s1, s4} y {s2, s3}. Observe que el conjunto de clases de 2-equivalencia es igual al conjunto de clases de 1-equivalencia. Determinación de las clases de -equivalencia El ejemplo 12.3.2 ilustra la relativa facilidad con que se pueden encontrar los conjuntos de k-equivalencia. Pero para simplificar a un autómata de estado-finito necesita encontrar el conjunto de clases de -equivalencia de estados. El próximo teorema expresa que para algún entero K, el conjunto de clases de -equivalencia es igual al conjunto de clases de K-equivalencia. Teorema 12.3.2 Si A es un autómata de estado-finito, entonces para algún entero, K 0, el con- junto de clases de K-equivalencia de estados de A es igual al conjunto de clases de (K 1)-equivalencia de estados de A y para tales K, ambos conjuntos son iguales al conjunto de clases de -equivalencia de estados de A. La demostración detallada del teorema 12.3.2 es algo técnica, pero no es difícil entender la idea de la demostración. El teorema 12.3.2 se sigue del hecho de que para cada entero positivo k, las clases de k-equivalencia se obtienen al subdividir las clases de (k ฀ 1)-equivalencia de acuerdo a una cierta regla que es la misma para cada k. Como es finito el número de estados del autómata, entonces este proceso de subdivisión no puede continuar indefinidamente y así para algún entero K 0, el conjunto de clases de K-equivalencia es igual al conjunto de clases de (K 1)-equivalencia. Además, el conjunto de clases de m-equivalencia es igual al conjunto de clases de K-equivalencia para cada entero m K. Pero esto implica que el conjunto de clases de -equivalencia es igual al conjunto de clases de K-equivalencia. Ejemplo 12.3.3 Determinación de las clases de -equivalencia de R Sea A el autómata de estado-finito definido en el ejemplo 12.3.2 Encuentre las clases de -equivalencia de estados de A. Solución De acuerdo al ejemplo 12.3.2, el conjunto de clases de 1-equivalencia para A es igual al conjunto de clases de 2-equivalencia. Por el teorema 12.3.2, entonces, el conjunto de clases de -equivalencia también es igual al conjunto de clases de 1-equivalencia. Así que: las clases de -equivalencia son {s0},{s1, s4} y {s2, s3}. En la notación de la sección 8.3, las clases de equivalencia se denotan por: [s0] {s0} [s1] {s1, s4} [s4] [s2] {s2, s3} [s3]. El autómata cociente Definamos el autómata cociente A de un autómata A. Sin embargo, para que todas las partes de la definición tengan sentido, debemos puntualizar dos hechos: Ninguna clase de -equivalencia de estados de A puede tener tanto estados aceptables como no-aceptables. 12.3.7 La razón de que esto sea verdad es que las clases de 0-equivalencia dividen al conjunto de estados de A en estados aceptables y no-aceptables y las clases de -equivalencia son subconjuntos de clases de 0-equivalencia. Si dos estados son -equivalentes, entonces sus estados-próximos también son -equivalentes para cualquier símbolo de entrada m. 12.3.8 Esto es verdadero por la siguiente razón. Suponga que los estados s y t son -equivalentes. Entonces cualquier cadena de entrada que envía A a un estado aceptable cuando A está en el estado s, manda A a un estado aceptable cuando A se encuentra en el estado t. Ahora suponga que m es cualquier símbolo de entrada y considere los estados-próximos N(s, m) y N(t, m). Introduciendo en A una cadena de longitud k, cuando A está en el estado N(s, m) o N(t, m), produce el mismo efecto que al introducir en A una cierta cadena de longitud (k 1) cuando A se encuentra en el estado s o t (a saber, la concatenación de m con la cadena de longitud k). Así que cualquier cadena que envía A hacia un estado aceptable cuando A está en el estado N(s, m) también manda A hacia un estado aceptable cuando A se encuentra en el estado N(t, m). Se tiene que N(s, m) y N(t, m) son -equivalentes. Las demostraciones completas de las propiedades (12.3.7) y (12.3.8) se dejan como ejercicios. Ahora podemos definir el autómata cociente A de A. Él es el autómata de estado-finito cuyos estados son las clases de -equivalencia de estados de A, tal que el estado inicial es la clase de -equivalencia conteniendo el estado inicial de A, cuyos estados aceptables son de la forma [s] en donde s es un estado aceptable de A y los símbolos de entrada son los mismos que los símbolos de entrada de A y su función de siguiente estado se deduce de la función de siguiente estado para A en la siguiente forma: Para encontrar el siguiente estado de A para un estado s y un símbolo de entrada m, elegir cualquier estado t en [s] y ver a qué siguiente estado va A si m es entrada cuando A se encuentra en el estado t; la clase de equivalencia de este estado es el siguiente estado de A . Definición Sea A un autómata de estado-finito con conjunto de estados S, conjunto de símbolos de