Clase 2

Clase 2.
Autómatas Finitos.
Definición.
Autómatas Finitos Determinísticos.
Lenguaje aceptado por un Autómata.
Equivalencia de autómatas.
Minimización de AFD.
Autómatas Finitos
• Cinco componentes: A = Q, , q0 , F , d 
• Q= conjunto de estados
• ∑= conjunto de símbolos terminales
• q0= estado inicial del autómata
• F= conjunto de estados finales
• d = función de transición.
• Se define de Qx ∑U{𝜆}→P(Q) (en general)
Función de transición. Representación.
Tabla: Grafo:
δ 0 1 - Nodos: representan estados.

q0 q1 t - Nodo doble: estado final.
q1 q 2  q 3 
q2 t q 3 
* q3 t t - El estado inicial señadado con una flecha.
- Los arcos dirigido representan la función de transición, etiqueta
sobre el arco indica qué se consumió de la entrada al efectuar esa
transición.
Autómatas Finitos Determinísticos
• Función de transición: 𝜹
d se define de Qx ∑→Q
• Función de transición extendida: 𝛿መ se define de Qx ∑*→Q

Describe lo que ocurre cuando se parte de cualquier estado y se sigue una
secuencia de entradas.
෡ 𝑞, 𝜆 = 𝑞
BASE: 𝜹
෡ 𝑞, 𝛚 = 𝛿 𝜹
PASO INDUCTIVO: 𝐒𝐢 𝛚 = 𝝎′ 𝒂, 𝜹 ෡ 𝑞, 𝜔′ , 𝒂 )
Función de transición extendida: 𝛿መ
Ejemplo: M = (q 0 ,q1,q 2 ,q3 ,t,0,1,d ,q 0 ,q3 )

(
dˆ(q 0 , "001" ) = d dˆ(q 0 , "00" ),1 )
(
dˆ(q 0 , "00" ) = d dˆ(q 0 , "0" ),0 )
(
dˆ(q 0 , "0" ) = d dˆ(q 0 ,  ),0 )
dˆ(q 0 ,  ) = q 0
Por lo tanto, queda:
( )
dˆ(q 0 , "0" ) = d dˆ(q 0 ,  ),0 = d (q 0 ,0 ) = q1
( )
dˆ(q 0 , "00" ) = d dˆ(q 0 , "0" ),0 = d (q1,0 ) =q 2
( )
dˆ(q 0 , "001" ) = d dˆ(q 0 , "00" ),1 = d (q 2 ,1) =q 3 Es decir, dˆ(q 0 , "001" ) =q 3
Configuración instantánea
La configuración instantánea es una descripción del autómata finito en un

momento dado.
Se denota con un par 𝑞, 𝜔 , donde 𝑞 ∈ 𝑄 ∧ ω ∈ Σ ∗
El símbolo ↦ indica el movimiento válido entre dos configuraciones.
Es decir: q, a   p,   d (q, a ) = p

Secuencia de configuraciones.
BASE: Si I es una configuración instantánea, I ↦* I es una secuencia de configuraciones.

PASO INDUCTIVO: Si K ↦* J es una secuencia de configuraciones válida y existe alguna
configuración K tal que I ↦ K es un movimiento válido entre dos configuraciones, entonces I ↦* J
es una secuencia de configuraciones válida.
Ejemplo: M = (q 0 ,q1,q 2 ,q3 ,t,0,1,d ,q 0 ,q3 )
q0 ,"001"  q1,"01"  q2 ,"1"  q3 , 

Es decir: q0 ,"001"  *q3 , 
Lenguaje aceptado por un autómata finito.
Mediante secuencia de configuraciones:
L =    * /q0 ,  *p, , p  F 
Mediante función de transición extendida:

L =    * /dˆ(q 0 , )  F 
Equivalencia de autómatas.
Dos AFD M y M’ son equivalentes si y sólo si L(M)=L(M’)
Es decir, los dos autómatas aceptan el mismo lenguaje.
Lenguaje aceptado por un autómata
• Sea: A = Q, , q0 , F , d 
• Con:
• Q={I,A,F}
• ∑={a,b}
• Estado inicial: I
• F ={F} d a b
• Función de transición dada por la tabla. I A F
A A I
F A F
Lenguaje aceptado por un autómata
• Q={I,A,F} d a b
• ∑={a,b} I A F
• Estado inicial: I A A I
• F ={F} F A F
• Función de transición dada por la tabla.
• ¿La palabra ‘ababb’ pertenece al lenguaje?

• [I,ababb] →[A,babb] →[I,abb] →[A,bb] →[I,b] →[F,]
• Pertenece!
Equivalencia de Autómatas.
• Dos AFD M y M’ son equivalentes si y sólo si L(M)=L(M’)

• Es decir, dos autómatas M y M’ son equivalentes si y sólo si
reconocen el mismo lenguaje.
• Si una palabra es reconocida en uno y en otro no, no son
equivalentes.
• La minimización de dos autómatas equivalentes es única.
1º Eliminar estados inaccesibles desde q0.

2º Construir el conjunto de clases de equivalencia de estados.
Estados Accesibles.
• Un estado 𝑞𝑖 ∈ 𝑄 es accesible si: ∃𝛼 ∈ 𝛴 ∗ |𝛿መ 𝑞0 , 𝛼 = 𝑞𝑖 ∈ 𝑄

∗
• Un estado 𝑞𝑖 ∈ 𝑄 es accesible si: ∃𝛼 ∈ 𝛴∗ | 𝑞0 , 𝛼 ՜ 𝑞𝑖 , 𝜆
CONSTRUCCIÓN INDUCTIVA.
BASE: El conjunto de un solo elemento 𝑄′ = 𝑞0 es accesible ya que

∃𝜆 ∈ 𝛴 ∗ |𝛿መ 𝑞0 , 𝜆 = 𝑞0 ∈ 𝑄
PASO INDUCTIVO: Si 𝑆 ⊆ 𝑄 es un conjunto de estados accesibles, ∀𝑎 ∈
Σ ∧ 𝑞𝑖 ∈ 𝑆, 𝑆 ′ = {𝑞𝑗 ∈ 𝑄 |𝛿 𝑞𝑖 , 𝑎 = 𝑞𝑗 } es de estados accesibles.
Estados Equivalentes o Indistinguibles.
• Un estado 𝑝 ∈ 𝑄 es indistinguible de q ∈ 𝑄 si:

∀𝜔 ∈ Σ ∗ : 𝛿መ 𝑝, 𝜔 ∈ 𝐹 ⇔ 𝛿መ 𝑞, 𝜔 ∈ 𝐹
• Un estado 𝑝 ∈ 𝑄 es distinguible de q ∈ 𝑄 si:

∃𝜔 ∈ Σ ∗ |𝛿መ 𝑝, 𝜔 ∈ 𝐹 ∧ 𝛿መ 𝑞, 𝜔 ∉ 𝐹
• o viceversa:
∃𝜔 ∈ Σ ∗ |𝛿መ 𝑝, 𝜔 ∉ 𝐹 ∧ 𝛿መ 𝑞, 𝜔 ∈ 𝐹
Propiedades de la indistinguibilidad.
La relación de indistinguibilidad es una relación de equivalencia.
• Propiedad Reflexiva: p es indistinguible de p.

∀𝜔 ∈ Σ ∗ : 𝛿መ 𝑝, 𝜔 ∈ 𝐹 ⇔ 𝛿መ 𝑝, 𝜔 ∈ 𝐹
• Propiedad Simétrica: si p es indistinguible de q, q es indistinguible de p.
• Que p sea indistinguible de q, significa que ∀𝜔 ∈ Σ ∗ : 𝛿መ 𝑝, 𝜔 ∈ 𝐹 ⇔ 𝛿መ 𝑞, 𝜔 ∈ 𝐹
• Que q sea indistinguible de p, significa que ∀𝜔 ∈ Σ ∗ : 𝛿መ 𝑞, 𝜔 ∈ 𝐹 ⇔ 𝛿መ 𝑝, 𝜔 ∈ 𝐹
• Propiedad Transitiva: si p es indistinguible de q, y q es indistinguible de r,
entonces p es indistinguible de r.
• Suponemos que p y r son distinguibles.
• Se contradice la hipótesis.
Indistinguibilidad de orden k.
Considera palabras de una misma longitud k.
La indistinguibilidad de orden k Ek es una relación de equivalencia.

Determina una partición del conjunto Q en clases de equivalencia.
𝑄
Lema 1: Dado un autómata, se cumple que = {𝐹, 𝑄 − 𝐹}
𝐸0
𝑝𝐸0 𝑞 significa que: ∀𝜔 ∈ Σ ∗ ∧ 𝜔 = 0: 𝛿መ 𝑝, 𝜆 ∈ 𝐹 ⇔ 𝛿መ 𝑞, 𝜆 ∈ 𝐹
መ 𝛿መ 𝑝, 𝜆 = 𝑝 ∧ 𝛿መ 𝑞, 𝜆 = 𝑞
Por definición de 𝛿,
Por lo tanto:
𝑝𝐸0 𝑞 significa que 𝑝 ∈ 𝐹 ⇔ 𝑞 ∈ 𝐹
Indistinguibilidad de orden k.
Lema 2: Dado un autómata y dos estados p y q:
𝑝𝐸𝑛+1 𝑞 ⇔ ∀𝑎 ∈ Σ: 𝛿 𝑝, 𝑎 𝐸𝑛 𝛿 𝑞, 𝑎
Si ∀𝑎 ∈ Σ: 𝛿 𝑝, 𝑎 𝐸𝑛 𝛿 𝑞, 𝑎 , eso significa que:

∀𝜔 ∈ Σ ∗ ∧ 𝜔 = 𝑛: 𝛿መ 𝑟, 𝜔 ∈ F ⇔ 𝛿መ 𝑠, 𝜔 ∈ 𝐹, siendo 𝛿 𝑝, 𝑎 = 𝑟 ∧ 𝛿 𝑞, 𝑎 = 𝑠
Por lo tanto:
∀𝜔′ ∈ Σ ∗ ∧ 𝜔′ = 𝑎𝜔, 𝜔′ = 𝑛 + 1: 𝛿መ 𝑝, 𝜔′ ∈ F ⇔ 𝛿መ 𝑞, 𝜔′ ∈ 𝐹,
Es decir,𝑝𝐸𝑛+1 𝑞
Construcción del conjunto cociente.
Entrada: Q
𝑸
Salida: Conjunto cociente de Q por la relación de indistinguibilidad.
𝑬
𝑄
1. 𝐸0
= 𝐹, 𝑄 − 𝐹
𝑄 𝑄
2. Generar a partir de de la siguiente manera:
𝐸𝑖+1 𝐸𝑖
𝑄
Los estados p y q pertenecen a la misma clase en ⇔
𝐸𝑖+1
𝑄
- 𝑝 y 𝑞 pertenecen a la misma clase en y
𝐸𝑖
𝑄
- ∀𝑎 ∈ Σ, 𝛿 𝑝, 𝑎 𝑦 𝛿(𝑞, 𝑎) pertenecen a la misma clase en
𝐸𝑖
𝑄 𝑄 𝑄 𝑄
3. Si = , entonces = . Sino, volver al paso 2.
𝐸𝑖+1 𝐸𝑖 𝐸𝑖+1 𝐸
Entrada:𝐴 =< 𝑄, Σ, 𝛿, 𝑞0 , 𝐹 >
Salida:𝐴′ =< 𝑄′, Σ, 𝛿′, 𝑞0 ′, 𝐹′ >equivalente a A con mínima cantidad de estados.
1. Eliminar estados inaccesibles desde 𝑞0
𝑄
2. Construir el conjunto cociente .
𝐸
3. 𝐴′ =< 𝑄′, Σ, 𝛿′, 𝑞0 ′, 𝐹′ > donde:
𝑄
• 𝑄′ = 𝐸
𝑄
• 𝑞0′ es el elemento de tal que 𝑞0 ∈ 𝑞0′ (la clase donde está 𝑞0 )
𝐸
𝑄
• 𝐹 ′ = {𝑠 ∈ 𝐸 ∧ 𝑆 ∩ 𝐹 ≠ ∅}
• 𝛿 ′ 𝑠𝑖 , 𝑎 = 𝑠𝑗 ⇔ ∃𝑝 ∈ 𝑠𝑖 ∧ ∃𝑞 ∈ 𝑠𝑗 |𝛿 𝑝, 𝑎 = 𝑞
Teorema
El autómata A’ obtenido con el algoritmo anterior es equivalente al autómata A y es
mínimo (el número de estados de A’ es menor o igual que el de cualquier otro AFD
equivalente a A).
Demostración
1. Demostrar equivalencia.
2. Suponer que existe un autómata 𝐴" =< 𝑄", Σ, 𝛿", 𝑞0 ", 𝐹" > equivalente a A’ con
menos estados.
መ 0 ′, 𝛼) = 𝑝 y 𝛿(𝑞
Sean 𝛼 y 𝛽 tales que 𝛿(𝑞 መ 0 ′, 𝛽) = 𝑞 en A’,
መ 0 ", 𝛼) = 𝛿(𝑞
pero 𝛿(𝑞 መ 0 ", 𝛽) = 𝑟 en A”.
Como A’ fue obtenido por el algoritmo, se sabe que p y q son distinguibles. Por lo
tanto A’ aceptaría 𝛼𝜔 pero no 𝛽𝜔.
መ 0 ", 𝛼𝜔) = 𝛿(𝑞
Sin embargo, en A”, 𝛿(𝑞 መ 0 ", 𝛽𝜔),aceptando ambas o rechazando ambas.

Clase 2

Cargado por

Copyright:

Formatos disponibles

Clase 2

Cargado por

Información del documento

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

Clase 2

Cargado por

Copyright:

Formatos disponibles

Clase 2.

δ 0 1 - Nodos: representan estados.

• Función de transición extendida: 𝛿መ se define de Qx ∑*→Q

Ejemplo: M = (q 0 ,q1,q 2 ,q3 ,t,0,1,d ,q 0 ,q3 )

La configuración instantánea es una descripción del autómata finito en un

Se denota con un par 𝑞, 𝜔 , donde 𝑞 ∈ 𝑄 ∧ ω ∈ Σ ∗

El símbolo ↦ indica el movimiento válido entre dos configuraciones.

Es decir: q, a   p,   d (q, a ) = p

BASE: Si I es una configuración instantánea, I ↦* I es una secuencia de configuraciones.

q0 ,"001"  q1,"01"  q2 ,"1"  q3 , 

Mediante secuencia de configuraciones:

L =    * /q0 ,  *p, , p  F 

Mediante función de transición extendida:

• ¿La palabra ‘ababb’ pertenece al lenguaje?

• Dos AFD M y M’ son equivalentes si y sólo si L(M)=L(M’)

1º Eliminar estados inaccesibles desde q0.

• Un estado 𝑞𝑖 ∈ 𝑄 es accesible si: ∃𝛼 ∈ 𝛴 ∗ |𝛿መ 𝑞0 , 𝛼 = 𝑞𝑖 ∈ 𝑄

BASE: El conjunto de un solo elemento 𝑄′ = 𝑞0 es accesible ya que

• Un estado 𝑝 ∈ 𝑄 es indistinguible de q ∈ 𝑄 si:

• Un estado 𝑝 ∈ 𝑄 es distinguible de q ∈ 𝑄 si:

La relación de indistinguibilidad es una relación de equivalencia.

• Propiedad Reflexiva: p es indistinguible de p.

Considera palabras de una misma longitud k.

La indistinguibilidad de orden k Ek es una relación de equivalencia.

Si ∀𝑎 ∈ Σ: 𝛿 𝑝, 𝑎 𝐸𝑛 𝛿 𝑞, 𝑎 , eso significa que:

También podría gustarte