EQUIVALENCIA ENTRE GRAMÁTICAS

TEOREMA  DE  MYHILL- NERODE Y MINIMIZACIÓN DE AUTÓMATAS FINITOS

Podemos asociar con un lenguaje cualquiera L una relación de equivalencia natural  RL; es decir, x  R L  y si y sólo si para cada z, xz  yz están en L o no lo están. En el peor de los casos cada cadena está, por sí misma, en una clase de equivalencia, pero puede haber menos clases. En particular, el índice (número de clases de equivalencia) siempre es finito si L es un conjunto regular.

Existe también una relación de equivalencia natural sobre las cadenas asociadas con un autómata finito. Sea M = (Q,S,d, q0, F) un DFA. Para y en S* sea x RMy si y sólo si d (q 0 , x ) = d (q 0 , y ). La relación RM es reflexiva, simétrica y transitiva, puesto que el símbolo " = " tiene tales propiedades, y por tanto RM es una relación de equivalencia. RM divide el conjunto S* en clases de equivalencia, una por cada estado que se puede alcanzar desde qa. Además, si x RM y, entonces xz RMyz para toda z en S*, ya que:

d(q0, xz) = d(d(q0, x), z) = d(d(q0, y), z) = d(q0, yz).

Una relación de equivalencia R tal que xRy implique xzRyz se dice que es invariante por la derecha (con respecto a la concatenación). Vemos que cada autómata finito induce una relación de equivalencia invariante por la derecha, definida como se definió RM sobre las cadenas de entrada. Este resultado se formaliza en el siguiente teorema.

Teorema  (Teorema de Myhill-Nerode) Las tres proposiciones siguientes son equivalentes:

  1. El conjunto L c S* es aceptado por algún autómata finito.

  2. L es la unión de algunas clases de equivalencia de una relación de equivalencia invariante por la derecha de índice finito.

  3. Sea RL la relación de equivalencia definida por: x R ¡y si y sólo si para toda z en S* , xz está en L exactamente cuando yz está en L. Entonces RL es de índice finito.

i) x y y tienen un 1 cada una, o

ii) x y y tienen cada una más de un 1.

Por ejemplo, si  x = 010 y y = 1000, entonces x z está en L si y sólo si z está en 0*. Pero yz está en L bajo exactamente las mismas condiciones. Como otro ejemplo, si x =01 y  y = 00, entonces podemos escoger z = O para mostrar que xRLy es falso. Esto es, xz  = 010 está en L, pero yz = 000 no lo está.

Podemos representar las tres clases de equivalencia de RL con C, = 0*, C2 = 0 *10 y C3 = 0 *10 *1 (0 + 1 )*, L es el lenguaje que consiste en sólo una de estas clases, C2. En la Fig. 3.3 se ilustra la relación de Ca, ..., Cf con C1, C2 y C3. Por ejemplo, Ca  U Cb = (00 )* + (00) *0 = 0* = C,.

A partir de RL podemos construir un DFA de la manera siguiente. Tómense representantes de C1, C2 y C3, digamos e, 1 y 11. Entonces sea M' el DFA que se muestra en la Fig. 3.4. Por ejemplo, d' ([1], 0) = [1], ya que si w es cualquier cadena de [1] (nótese que [ 1 ] es C1), digamos Oi 10j, entonces w O es Oi 10j *', que también está en C=0*10*.

Minimización de autómatas finitos

El teorema de Myhill-Nerode tiene, entre otras consecuencias, la implicación de que existe un DFA de estado mínimo esencialmente único cada conjunto regular.

Teorema El autómata de estado mínimo que acepta a un conjunto L es único hasta un isomorfismo (es decir, un renombramiento de estados) y está dado como M 'en la demostración del Teorema

Demostración En la demostración del Teorema vimos que cualquier DFA M' = (Q,S, d,q 0, F) que acepta a L define una relación de equivalencia que es un refinamiento de RL. Por consiguiente el número de estados de M es mayor o igual que el número de estados de M' del Teorema. Si la igualdad es válida, entonces cada uno de los estados de M' puede ser identificado con uno de los estados de M'. Esto es, sea q un estado de M. Debe existir alguna x en S*, tal que d(q 0 , x ) = q, de otra manera q puede ser eliminada de Q, y hallar, así, un autómata más pequeño. Identifiquese a q con el estado d (q O, x ) de M'. Esta identificación será consistente. Si d(^0, z)= d(q0 , y) = q, entonces, según la demostración del teorema, x. y  y está en la misma clase de equivalencia de rl. En consecuencia, d' (q0' , x) = d'(q'0   , y).

Un algoritmo de minimización

Existe un método simple para encontrar el DFA de estado mínimo M' de los Teoremas anteriores, equivalente a un DFA dado M = (Q, S, d, q 0, F). Sea el símbolo = la relación de equivalencia sobre los estados de M, tal que p = q si y sólo si para cada cadena de entrada x, d (p,x) es un estado de aceptación si y sólo si d (q, x) es un estado de aceptación. Obsérvese que existe un isomorfismo entre aquellas clases de equivalencia de = que contienen un estado que se puede alcanzar desde q0  mediante alguna cadena de entrada y los estados del FA de estado mínimo M'. Así pues los estados de Así pueden identificarse con estas clases.

Más que dar un algoritmo formal para encontrar las clases de equivalencia = de primero veremos un ejemplo. En primer lugar se necesita cierta terminología. Si p=q, decimos que p es equivalente a q. Decimos que p es distinguible de q si existe una x tal d(p, x ) esté en F y d(q, x ) no, o viceversa.

Ejemplo  Sea M el autómata finito que se muestra en la Fig. 3.5. En la Fig. 3.6 hemos construido una tabla con una entrada por cada par de estados. Ponemos una X en la tabla cada vez que descubrimos un par de estados que no pueden ser equivalentes. Inicialmente se sitúa una X en cada entrada que corresponda a un estado final y uno no final. En nuestro ejemplo, ponemos una X en las entradas (a, c), (b , c), (c , d), (c , e), (c ,f), (c,g) y (c,h).

En seguida, para cada par de estados p y q que aún no se sabe si son distinguibles, consideramos los pares de estados r = d(p ,a)y s = d(q ,á) para cada símbolo de entrada a . Si se ha mostrado que los estados r y s son distinguibles mediante alguna cadena x, entonces p y q son distinguibles mediante la cadena a x. Por consiguiente si la entrada (r, s) de la tabla tiene una X, también se debe poner una en la entrada (p, q). Si la entrada (r , s) aún no tiene una X, entonces el par (p , q) se coloca en una lista que está asociada con la entrada (r, s), si en lo futuro, la entrada (r , s) recibe una X, entonces cada par de la lista asociada con la entrada (r, s) también deberá tener una X.

continuando con el ejemplo, colocamos una X en la entrada (a, b), puesto que la entrada (d(b , 1), d (a , 1)) = (c ,f) ya tiene una X. De forma similar, la entrada (a , d) recibe una X ya que la entrada (d (a ,0), d(d , 0) = (b , c ) tiene una. Tomando en consideración la entrada (a, e) sobre el símbolo de entrada 0 trae como resultado que el par (a, e) sea colocado en la lista de los pares asociados con (b,h). Obsérvese que sobre la entrada 1, tanto a como e van al mismo estado/ y en consecuencia ninguna cadena que comience con un 1 puede distinguir a de e . Debido a la entrada 0, el par (a , g) se coloca en la lista asociada con (b, g). Cuando se considera la entrada (b, g), ésta recibe una X debido a una entrada 1, y por tanto el par (a, g) también debe tener una X, pues está en la lista asociada con (b , g). La cadena 01 distingue a de g.

Al completar la tabla de la Fig. 3.6, concluimos que los estados equivalentes son a = e,b = h y d =f. En la Fig. 3.7 se da el autómata finito de estado mínimo.