Minimización de autómatas

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Minimizacion se aplica solamente a AFD, no existe equivalente sobre AFND. Tambien es necesario que el AFD no tenga estados inalcanzables (debe haber un camino orientado desde el estado inicial hacia cualquier otro).

Se basa en el concepto de estados indistinguibles. Dos estados son indistinguibles sii para cualquier cadena, partiendo de esos estados se llega siempre o a finales o a no finales. Vale que los estados a los que se llegan son tambien indistinguibles. Indistinguibilidad es una relacion de equivalencia.

Indistiguibilidad[editar]

Sea M = <Q, Σ,Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta} ,Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q_0} ,F> un AFD, los estados q,r Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \in} Q son indistinguibles si y solo si: para toda cadena Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alpha} , partiendo de q se llega a un estado final si y solo si partiendo de r tambien se llega a un estado final.

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q \equiv r \leftrightarrow \forall \alpha \in \Sigma^*, (\hat \delta(q,\alpha) \in F \leftrightarrow \hat \delta(r,\alpha) \in F)}

Relación de equivalencia[editar]

La relación de indistinguibilidad es reflexiva, simétrica y transitiva. Con lo cual es una relación de equivalencia.

  • Reflexiva

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall \alpha \in \Sigma^*, (\hat \delta(q,\alpha) \in F \leftrightarrow \hat \delta (q,\alpha) \in F) \rightarrow q \equiv q}

  • Simétrica

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q \equiv r \rightarrow \forall \alpha \in \Sigma^*, (\hat \delta(q,\alpha) \in F \leftrightarrow \hat \delta (r,\alpha) \in F ) \leftrightarrow \forall \alpha \in \Sigma^*, (\hat \delta(r,\alpha) \in F \leftrightarrow \hat \delta (q,\alpha) \in F ) \rightarrow r \equiv q }

  • Transitiva

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q \equiv r \rightarrow \forall \alpha \in \Sigma^*, (\hat \delta(q,\alpha) \in F \leftrightarrow \hat \delta(r,\alpha) \in F) }

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle r \equiv s \rightarrow \forall \alpha \in \Sigma^*, (\hat \delta(r,\alpha) \in F \leftrightarrow \hat \delta(s,\alpha) \in F) }

entonces se deduce que:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall \alpha \in \Sigma^*, (\hat \delta(q,\alpha) \in F \leftrightarrow \hat \delta(s,\alpha) \in F) \rightarrow q \equiv s}

Indistinguibilidad de los pares de estados siguientes[editar]

Todo par de estados indistinguibles, al consumirse cualquier cadena Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alpha} , llevan a otro par de estados indistinguibles

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q \equiv r \rightarrow \forall \alpha \in \Sigma^*, (\hat \delta(q,\alpha) \equiv \hat \delta(r,\alpha))}

Demostración por absurdo

Supongamos que

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exist \alpha \in \Sigma^*,(\hat \delta(q,\alpha) \not \equiv \hat \delta(r,\alpha))}

entonces

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exist \beta \in \Sigma^*,(\hat \delta(\hat \delta(q,\alpha),\beta) \in F \and \hat \delta(\hat \delta(r,\alpha),\beta) \not \in F) }

o viceversa, que es equivalente a decir

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat \delta(q,\alpha\beta) \in F \and \hat \delta(r,\alpha\beta) \not \in F}

o viceversa. Lo cual es un absurdo, ya que implica que Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q \not \equiv r} al existir una cadena Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alpha\beta} por la cual q se pueda distinguir de r.

Indistinguibilidad de orden K[editar]

Es análogo a indistinguibilidad pero sujeto a cadenas de longitud a lo sumo K.

Relacion de equivalencia[editar]

Al igual que indistinguibilidad, es una relacion de equivalencia (reflexiva, simetrica y transitiva). La demostracion es trivial.

K+1 implica K[editar]

La relacion de orden K+1 esta contenida no estrictamente en la de orden K. Si dos estados son indistinguibles respecto de cadenas de longitud a lo sumo K+1, entonces, en particular, lo son para cadenas de longitud a lo sumo K.

Cociente por orden 0[editar]

El conjunto de estados de un automata, cocientado por la relacion de indistinguibildad de orden 0, lo separa en dos clases de equivalencia: los finales y los no finales.

K+1 sii K por todo terminal[editar]

Dos estados p y r son indistinguibles de orden K+1 sii para todo terminal a vale que los estados que se alcanzan a partir de consumir a por p y r son indistinguibles de orden K. Esto permite dar una definicion inductiva de indistinguibilidad.

La ida se prueba por absurdo. Si existe un terminal a tal que al consumirlo se llega a dos estados p' y r' distinguibles por alguna cadena alfa de longitud a lo sumo K, entonces la cadena a + alfa distingue K+1 a p y r, lo que contradice la hipotesis.

La vuelta tambien se puede probar por absurdo. Si p y r son distinguibles por alfa de longitud K+1, entonces p' y r' , alcanzados tras consumir el primer caracter de alfa, son distinguibles por el resto de alfa, que tiene longitud a lo sumo K, lo que contradice la hipotesis.

K+1 = K implica K+n = K[editar]

Si para cualquier par de estados q y p vale que la relacion de indistinguibilidad de orden K+1 es igual a la de orden K, entonces cualquier indistinguibilidad de orden superior seguira siendo igual. Esto da un criterio de corte para la definicion inductiva de indistinguibilidad de orden K, y permite generalizar de orden K a indistinguibilidad en general.

Puede demostrarse por induccion en n. El caso base es trivial. Para el paso inductivo, simplemente se usa que si dos estados son indistinguibles orden k+n+1, entonces los estados a los que se llega por cualquier terminal lo son orden k+n, y luego se aplica la hipotesis inductiva.

Intuitivamente, esto sucede pues indistinguibilidad de orden K permite distinguir a todos los estados que estan a "distancia" K de algun estado final. Al pasar a K+1, se agregan todos los estados que están a un paso más. Si no hay cambios, es porque ya se cubrieron todos los estados del automata, y no es necesario tener cadenas mas largas para distinguirlos.

Automata Minimo[editar]

Un automata minimo se logra tomando como estados las clases de equivalencia generadas por la relacion de indistinguibilidad en el automata original. Las transiciones en el nuevo automata se definen como Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta \prime ([q], a) = [ \delta (q,a)]} , es decir, el estado alcanzable en el AFDM a partir de la clase [q] por el terminal a, es la clase que se alcanza por a a partir de todos los estados que conforman q en el AFD original.

Transiciones entre clases indistinguibles[editar]

Dada la definicion de funcion de transicion anterior, vale la equivalencia tambien para la funcion de transicion extendida. Esto es, si en el AFD original se llegaba al estado r desde q por la cadena alfa, entonces en el minimo se llega a la clase de equivalencia de r desde q via alfa.

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat \delta (q,a) = r \Longrightarrow \hat \delta \prime ([q],a) = [r]}

Se demuestra por induccion en la longitud de la cadena. El caso base (longitud cero) es trivial. Para el paso inductivo, se parte la cadena en a + alfa, y se aplica la definicion de la funcion no extendida (sobre a) junto con la hipotesis inductiva (sobre alfa), mas propiedades de la funcion de transicion extendida.

Cantidad de estados[editar]

Dados dos AFDs M y M', si para todo par de cadenas que conducen a estados diferentes en M desde q0 tambien conducen a estados diferentes en M' desde q0', entonces M' debe tener tantos o más estados que M.

Para demostrarlo, se puede obtener una funcion inyectiva de Q en Q', esto es, alguna funcion que para todo estado de Q vaya a un estado de Q' y no repita imagenes. Esto garantiza que Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |Q| \leq |Q'|} .

Dicha funcion f(q) se puede definir como el estado que se alcanza en M' a desde q0' consumiendo la cadena g(q). La funcion g puede definirse como la menor cadena en M tal que al consumirla desde q0 se llegue al estado q; o sea, qué camino hay que seguir en M para llegar a q.

Como todas las cadenas generadas por g llevan a estados diferentes, entonces al consumirlas en M' tambien se llegan a estados diferentes (por hipotesis). Por lo tanto, se tiene la funcion inyectiva buscada.

Minimo[editar]

Se desea probar que el automata minimo construido a partir de las clases de equivalencia de la funcion de indistinguibilidad es efectivamente minimo. Esto es, que no existe ningun automata M' que reconozca el mismo lenguaje que MR (siendo MR el automata reducido) y que tenga menos estados.

Por la demostracion anterior, esto implica que deberia existir un par de cadenas alfa y beta tales que lleven a estados distintos p y r en MR y a estados iguales en M'.

Al ser p y r estados distintos en MR, significa que son distinguibles, esto es, que hay una cadena que lleva a uno a un estado final y a otro a uno no final. Esto significa que al concatenar esta cadena a las dos alfa y beta que habian dado origen a p y r, se obtienen dos cadenas, las cuales una pertenece al lenguaje y la otra no.

Ahora bien, como p y r coinciden en M', cualquier cadena los lleva al mismo estado, sea final o no. Entonces, al realizar la misma concatenacion que antes, se llega a ambas cadenas pertenecen o no. Por lo tanto, M' no reconoce el mismo lenguaje que MR, absurdo que proviene de suponer que MR no era minimo en cantidad de estados.