Copyright: Ayuda creada por: Beatriz Corzo menéndez                1999


IM1

•	Descripción:

Algoritmo general que calcula el autómata cociente: A0 /Π Pr(s+)

Donde:

A0            árbol de prefijos PT(S+).

ΠPr(s+)    partición del conjunto de estados de A0, que viene determinada por su aplicación característica χ  , de forma que:

B ( u, ΠPr(s+) ) = B ( v, ΠPr(s+) ),  si y sóo si,   χ(u,v) =1

Existen diferentes heurísticos para definir distintas funciones características y por tanto diferentes particiones sobre PT(S+).

El autómata resultado del algoritmo IM1 será por lo general no determinístico y no mínimo.

•	Pseudocódigo:

———————————————————————————————————————

Entrada:     S+  Muestra positiva no vacía.

     k    parámetro del heurístico.

Salida:       A0 / ΠPr(s+)    Autómata finito reconocedor de un cierto lenguaje que contiene a S+.

———————————————————————————————————————

Procedimiento INICIALIZAR

A0 = (Q0, , 0, 0, F0)  =  PT(S+)    árbol de prefijos de S+

Π0 = Partición trivial en Q0. Cada elemento de Q0 es un elemento de la partición, cada 	conjunto contiene un solo elemento.

i = 0

Fin Procedimiento

Procedimiento JUNTAR

ParaCada (u,v) ∈ Q0 × Q0  hacer

Si  χ(u,v) =1  entonces

B1 = B ( u, Πi  )

B2 = B ( v, Πi  )

Π'i =  Πi - B1 - B2

Πi+1  = Π'i  + ( B1 ≡ B2 )

i = i + 1

Finsi

FinPara

f = i

retorna Πf   ( = Qi / Πi  )

Fin Procedimiento


Heuristicos
Heurísticos

•	K-sufijos (Biermann y Feldman)

χ(u,v) =1, sii, Tks+ (u) = Tks+ (v)   k = 0, 1, 2, ...

Una cota superior de k podría ser la longitud de la palabra más larga.

•	Levine

χ(u,v) =1, sii, stren(u,v) ≥  S, donde S es un valor de la imagen de la función stren.

•	Miclet

Heurístico general que, con la particularización que emplea Miclet, equivale al heurístico de Levine cuando se elige como S el menor valor no nulo de la tabla de la función stren.

•	Angluin

Es un heurístico para lenguajes K-reversibles.

χ(u,v) =1, sii, u, v  transgreden las condiciones de K-reversibilidad, es decir, cuando u, v están en una de las siguientes situaciones:

Nota: El IM1 se aplicaría con una implementación particular para este heurístico.


Particion sobre un conjunto de estados
ΠPr(s+)  es la restricción de ΠL al conjunto de prefijos de una muestra positiva S+. Se define como:

∀ u,v  ∈  Pr(S+)   B(u, ΠPr(s+) ) = B(v, ΠPr(s+) )  ⇔ TL(u) = TL(v)


Muestra Positiva
S+ = Conjunto finito tal que  S+  ⊂  L

es decir, cadenas que pertenecen al lenguaje, llamado también conjunto de ejemplos positivos.


Bloque
B(s, Πs) = Si   tal que s ∈ Si

Las aplicaciones se harán para s = estado.


Particion
Πs. Dado un conjunto S, una partición de S, es una colección de conjuntos


Automata Cociente
Autómata Cociente

A/Π = ( Q/Π, Σ, δ', I', F' )

Siendo Π una partición de Q, donde:

qi, qj  ∈  Q verificarán  qi  R qj  ⇔   B(qi, Π) = B(qj, Π)

( interpretación como una relación de equivalencia )

El autómata cociente puede resultar no determinístico.

Siendo:

Q/Π    Conjunto de estados

Σ        Alfabeto

δ'        Aplicación de la forma:    δ' : Q/Π × Σ   ——→  Q/Π

Si B1 ∈  Q/Π, es decir, un bloque de la partición Π en Q,

entonces

δ'(B1, x) = B2  ⇔   ∃ q ∈ B1, tal que, δ(q, x) = q' ∈ B2

I'    Estado inicial = Clase correspondiente al bloque B1

I' = [I] = B( I, Π)   bloque en el que está I con la relación Π.

Es decir, bloque en el que está el antiguo estado inicial.

F'   Estado final = { B ∈ Q/Π:  B ∩ F ≠ ∅ }, siendo B  bloques, clases o estados en el 	nuevo autómata.

Es decir, los estados finales ahora serán aquellos bloques que contengan 	alguno/s de el/los antiguo/s estado/s final/es, pudiendo contener otros estados que antes 	no eran finales.


Aceptor de Prefijos

Ejemplo

PT(S+) =(Q, Σ, δ, I, F)

Donde:

 Q    Conjunto de Estados = Pr(S+)

 Σ    Alfabeto.

 δ     Aplicación de la forma

δ : Q × Σ ——→ Q

     u , x    → δ (u , x) =  ux    si ux ∈  Pr(S+)

   	       =  ⊥     en otro caso

I     Estado inicial = λ  (la cadena vacía siempre es un prefijo)

F    Conjunto de estados finales = S+


Ejemplo de Aceptor de Prefijos
Ejemplo de Construcción de un Aceptor de Prefijos

Siendo  S+ = { ab, aab, abbb}

Se trata de obtener:  PT(S+) = ( Q, Σ, δ, I, F )

    Σ = {a,b}

    Q´= Pr(S+) = {  ab: λab, ab, abλ

 	     aab: λaab, aab, aab, aabλ

     abbb: λabbb, abbb, abbb, abbb, abbbλ  }

 	Nota: Los caracteres en negrita señalan los prefijos posibles para cada cadena.

    Q = Pr(S+) = { λ, a, ab, aa, aab, abb, abbb }   ⇒  7 estados

    δ : Q × Σ ——→  Q

         (u , x)   →      δ (u, x) = ux   si  ux  ∈ Pr(S+)

     δ (λ , a) = a    pues  a  ∈ Pr(S+)

     δ (λ , b) = ⊥   pues  b  ∉ Pr(S+)

.

.

.

Es decir, si 'a' ∈ Pr(S+) entonces está definido un arco en el autómata de la forma:

    I = λ

    F = S+ = {ab, aab, abbb}

El autómata quedaría: