Minimización de Afd

Integrantes: Sofía Cumbal Katherine Muñoz
Juan Góez Christian Diaz

Julián Rosero Nicole Romero
Rodrigo Puente Cristian Pujota
Jhonny Sánchez Jason
INTRODUCCIÓN
• Teorema 3.2.4
Dado un autómata finito
determinista, se puede obtener a
partir de él otro autómata
equivalente si se eliminan del
autómata todos los estados que
no sean accesibles desde el
estado inicial, así como todos los
arcos que parten de los estados
eliminados.
MOTIVOS PARA MINIMIZAR
• Es posible diseñar varios autómatas equivalentes, Los
algoritmos que implementan AFD suelen requerir un espacio
más o menos proporcional al número de estados del autómata,
por lo que interesa que el número de dichos estados sea el
menor posible, para abaratar costos y ganar eficiencia.
• El AFD minimal es único (misma estructura), por lo tanto, al
minimizar dos AFD podemos saber si su lenguaje es el mismo.
• Nos da una noción comparable de “complejidad” (comparando
el tamaño de los Afd minimales).
ALGORITMO:
• Paracada Afd existe un Afd con cantidad mínimade estados que acepta
el mismo lenguaje.
• El algoritmo de minimización divide el conjunto de estados del AFD en
clases de equivalencia. Los pasos a seguir son los siguientes:
•Eliminar los estados no alcanzables desde el estado

1) inicial.
•Eliminar los estados desde los cuales no es posible

2) alcanzar un estado final.
•Construir una partición 𝛱0 del conjunto de estados

3) (estados finales y no finales)
• (Sea K=0).Definir 𝛱𝑘+1 donde cada grupo G de una partición
𝛱𝑘 se divide a G en subgrupos tales que dos estados s y t
están en el mismo grupo sí y solo sí para todo símbolo a del
4) alfabeto de entrada, los estados s y t van al mismo grupo de

𝛱𝑘+1
• (Sea k=k+1). Si 𝛱𝑘 ≠ 𝛱𝑘−1 Volver al paso 5. En caso

contrario, terminar.
5)
• Nota: Puede haber dos tipos de estados innecesarios,

que es posible eliminar o combinar.
EJEMPLO TEORICO
Se elimina s ya que es un estado

inaccesible
X= {𝒒, 𝒓} estados aceptadores
Y= {𝒑} estados no aceptadores
𝜮 = {𝟎, 𝟏}
Y
0 1 0 1
q x y X Y
p x y
r x y
X
Nota
• Elresultado se llama cociente, por la
relación de equivalente, ya que agrupa
estados equivalentes y solo se preocupa de
sus transiciones. Para definir las
transiciones van de la clase de equivalencia
a otra clase de equivalencia y viene dada
por las transiciones de cualquiera de sus
miembros.
ALGORITMO DE LA
TABLA
Eliminar todos los estados no

alcanzables desde 𝑞0
Determinar los pares de estados

equivalentes
Mientras quede un par 𝑝 ≡ 𝑞, redirigir

hacia p todos los arcos que llegaban a q,
y luego eliminar q.
Para determinar los pares equivalentes usamos el “algoritmo de llenado
de tabla”.
La tabla contiene los pares (p,q). Se irá marcando los pares
distinguibles (no equivalentes)
Marcamos todos los pares en los que

un estado es de aceptación y el otro
no.
Para todo (p,q) no marcado y para
todo 𝛼 ∈ 𝛴, si (𝛿 𝑝, 𝛼 , 𝛿 𝑞, 𝛼 ) está
marcado →marcar (p,q)
Si en el anterior paso se marcó algo,
repetirlo
EJEMPLO A
EF D BC
B
C
D
F E D C B
A
B AD
C AD
D
E BC
EF D BC
A
B
C
D
Myhill-Nerode
Teorema de Myhill-Nerode:
Sea L* un lenguaje y sea u L v definida como
antes. Entonces L es regular ssi L es de índice finito.
Demostración:
(, La dirección fácil )
•L es regular   AFD M=(Q, , , q0, F), L=L(M)
 el índice de M es |Q|.
•Como cada clase de equivalencia de L está formada por
una o más clases de equivalencia de M, el índice de L
debe ser |Q| o menor.
Myhill-Nerode
Teorema de Myhill-Nerode:
Sea L* un lenguaje y sea u L v definida como
antes. Entonces L es regular ssi L es de índice finito.
Demostración:
() Definimos el AFD M=(Q, , , q0, F) mediante
•Q = */L, [el conjunto de clases de equivalencia de L ]
•q0 = []
•F = { qQ: qL}
•( [u], ) = [u]
PDQ: L(M)=L. Además veremos que M es mínimo.

Myhill-Nerode
Q = */L, [conjunto de clases de equivalencia de L ]
q0 = [], F = { qQ: qL}, ( [u], ) = [u]
PDQ L(M)=L.
Es decir, que u*, uL(M)  [u]L
Pero uL(M)  (q0,u)F  ([],u)L

así que estamos listos si demostramos que ([],u)=[u].
Demostraremos, más en general, que

u,v*, ([v],u)=[vu]
Myhill-Nerode
q0 = [], F = { qQ: qL}, ( [u], ) = [u]
PDQ u,v*, ([v],u)=[vu]
Inducción sobre |u| :
Base:
|u|=1. Cierto, por definición de .
Paso inductivo:
|u|>1, u=w para algún , w con |w|<|u|.
([v],u) = ([v],w) = (([v],w),) = ([vw],) = [vw] = [vu]
Definición Hipótesis de Definición

(recursiva) de  inducción de 
Myhill-Nerode
q0 = [], F = { qQ: qL}, ( [u], ) = [u]
Lo único que falta ver es que M es mínimo. Recordemos

que sus estados son las clases de equivalencia de L.
 Para cada par de estados [u], [v], existe una

palabra w que distingue las clases de equivalencia (si
no, serían la misma clase).
 uw y vw están una fuera y la otra dentro de L.
 [uw] y [vw] están uno fuera y otro dentro de F.
w también distingue los estados correspondientes.

Myhill-Nerode
¿Cuál es la intuición tras Myhill-
Nerode?
•Recibimos el input: u=vw
•Al terminar de verlo, debemos decidir
acaso uL.
•Hemos leído v, falta w.
•La relación L está definida de tal forma que lo único
que necesitamos saber (para cumplir con la tarea final)
es en cuál clase de equivalencia está v.
Myhill-Nerode 0
1 [v]
•La función  define como voy
actualizando esa información con
cada nueva letra que pasa. [v1] [v0]
•Myhill-Nerode lo que me dice es que

un lenguaje es regular ssi eso que
tengo que saber, momento a
momento, cabe en una memoria
finita.
La unicidad del AFD mínimo.
Teorema de minimización:
Sea L un lenguaje regular. Entonces dentro de los AFD que
reconocen a L, existe un único AFD que tiene la cantidad mínima
de estados, y es el que se obtiene a partir de cualquier otro
mediante la aplicación del algoritmode minimización.
Supongamos que partimos de dos AFD distintos,
ambos con el mismo lenguaje, y llegamos a dos AFD
minimales M y M’.
¿Qué significa que sean el mismo?

Significa que salvo “cambio de nombre”, los estados
son los mismos. Llamemos  al cambio de nombre.
0
 1
q 0
0 0 B
1 A
q1 0
1 0 1
q11 -1 1
C
1
Dados dos AFD M=(Q, , , q0, F) y M’=(Q’, , ’, q’0,
F’), son “el mismo” ssi existe :QQ’ biyectiva tal que
• (q0) = q’0  es un isomorfismo

• (F) = F’ entre M y M’.
• ((q,)) = ((q),)
En el ejemplo de abajo, (q)=A, (q11)=B, (q1)=C.

0
 1
q 0
0 0 B
1 A
q1 0
1 0 1
q11 -1 1
C
1
•Ser isomorfos (“ser el mismo”) es claramente una

relación de equivalencia entre AFD.
Para probar que dos AFD son isomorfos, sirve
probar que ambos son isomorfos a un tercero.
Usando Myhill-Nerode
Myhill-Nerode sirve por lo tanto para explicar el

algoritmo de minimización y su resultado.
Sin embargo, también se puede usar directamente,

como herramienta para demostrar que un cierto
lenguaje NO es regular.

Minimización de Afd

Cargado por

Copyright:

Formatos disponibles

Minimización de Afd

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Minimización de Afd

Cargado por

Copyright:

Formatos disponibles

Integrantes: Sofía Cumbal Katherine Muñoz

Juan Góez Christian Diaz

•Eliminar los estados no alcanzables desde el estado

•Eliminar los estados desde los cuales no es posible

•Construir una partición 𝛱0 del conjunto de estados

4) alfabeto de entrada, los estados s y t van al mismo grupo de

• (Sea k=k+1). Si 𝛱𝑘 ≠ 𝛱𝑘−1 Volver al paso 5. En caso

• Nota: Puede haber dos tipos de estados innecesarios,

Se elimina s ya que es un estado

Eliminar todos los estados no

Determinar los pares de estados

Mientras quede un par 𝑝 ≡ 𝑞, redirigir

Marcamos todos los pares en los que

PDQ: L(M)=L. Además veremos que M es mínimo.

Es decir, que u*, uL(M)  [u]L

Pero uL(M)  (q0,u)F  ([],u)L

Demostraremos, más en general, que

Definición Hipótesis de Definición

Lo único que falta ver es que M es mínimo. Recordemos

 Para cada par de estados [u], [v], existe una

w también distingue los estados correspondientes.

•Myhill-Nerode lo que me dice es que

¿Qué significa que sean el mismo?

• (q0) = q’0  es un isomorfismo

En el ejemplo de abajo, (q)=A, (q11)=B, (q1)=C.

•Ser isomorfos (“ser el mismo”) es claramente una

Myhill-Nerode sirve por lo tanto para explicar el

Sin embargo, también se puede usar directamente,

También podría gustarte