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


KC

•	Descripción

Es una variante del IM1. Dada una muestra positiva y un natural k, produce un aceptor K-contextual reconociendo a S+ al menos. En lenguajes K-contextuales es posible una muestra característica de una sola cadena, es decir, es posible inducir un lenguaje K-contextual a partir de una muestra positiva de una sola cadena.

Se define:

χ(u,v) = 1,  sii,   ∃ w,  | w | = k,   tal que:    u = u1w  y   v = v1w , siendo  |w| = k

χ(u,v) = 0, en otro caso

Nota: Obsérvese que χ(u,-) = 0 siempre que |u| < k

•	Pseudocódigo

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

Entrada:      S+  Muestra positiva no vacía.

       k    Parámetro.

Salida:        A    Autómata finito K-contextual.

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

Procedimiento INICIALIZAR

A0  = (Q0, Σ0, δ0, I0, F0)   =  PT(S0+)   árbol de prefijos de S0+

Π0 = { {u}: u ∈ Q0, |u| < k }

Q'0 = Qo - ∪ Π0

i = 0

Fin procedimiento

Procedimiento JUNTAR

ParaCada   Estado u1v   ∈  Q0 hacer

Si | v | = k entonces

Si existe algún bloque B1 tal que B1 = B(u2v,Πi)

entonces    B2 = B1 ∪ {u1v}

sino           B2 = {u1v}

Finsi

Πi+1  = Πi  - B1+ B2

i = i + 1

FinPara

f  =  i

retorna  A0 / Πf

Fin Procedimiento


KC Version Incremental
KC Versión Incremental

•	Pasos del Algoritmo

Sea S+ una muestra positiva y A el autómata obtenido como salida del algoritmo KC para esa muestra. Para la obtención del autómata inducido por KC para S+ ∪ {w} , es decir, con una nueva cadena añadida, se realizan los siguientes pasos:

1. Comprobar si w es reconocida por A, en caso afirmativo, parar. En otro caso seguir.

2. Construir un camino desde el estado inicial hasta un estado final nuevo reconociendo 	w y aprovechando en el primer tramo el camino que hubiese en A.

4. Ejecutar KC sobre el autómata resultante del paso 3.

•	Pseudocódigo

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

Entradas:      w  Cadena.

Salida:          A    Autómata finito K-contextual.

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

Procedimiento INICIALIZAR

S0+ = S0+  ∪   {w0}

Fin Procedimiento

Procedimiento INCREMENTAL

Si  EsReconocidaCadena( w0 )  entonces  FIN

sino

ParaCada  b ∈ w0 y partiendo de la primera transición indefinida

añadir nuevos estados y transiciones

FinPara

Marcar el último estado al que se llegó como final

InsertarPar (  LISTA, (estado, estadofinal de A)  )

Aplicar KC

FinSi

Fin Procedimiento


KC Version con Ejemplos Negativos
KC Versión con Ejemplos Negativos

•	Pasos del Algoritmo

Partiendo de una muestra de ejemplos positivos S+ y de otra muestra de ejemplos negativos S-, los pasos a seguir son:

1. K = 0,  K <  maxi  { longitud de cadenai  ∈  S+ }

2. Aplicar el algoritmo KC infiriendo lenguajes para K = 0..n.

3. Parar cuando se encuentre un lenguaje (Lk ) que contenga todas las cadenas de la 	muestra positiva y ninguna de las cadenas de la muestra negativa.

•	Pseudocódigo

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

Entradas:     S-, S+ muestras de ejemplos.

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

Procedimiento INICIALIZAR

Calcular longitudes de las cadenas de S+

k = 0

maxK = max { longitud de las cadenas de S+}

Continuar = TRUE

Fin Procedimiento

Procedimiento KREjemplosNegativos

Mientras ( k ≤ maxK )   AND   ( Continuar = TRUE )   hacer

Aplicar KC usando S+

NoReconocidas = TRUE

ParaCada   w ∈ S-  hacer

 	        NoReconocidas = NoReconocidas   AND   Not(EsReconocidaCadena( w ))

FinPara

Si   NoReconocidas = TRUE   entonces   Continuar = FALSE  FinSi

k = k + 1

FinMientras

Si   Continuar = FALSE   entonces    encontrada la solución para k = k -1

 sino    FALLO   no se encontró solución para ese rango de k

FinSi

Fin Procedimiento


Funcion EsReconocidaCadena
Función EsReconocidaCadena

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

Entradas:      w  Cadena.

Salida:          valor booleano.

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

Procedimiento INICIALIZAR

Reconocida = FALSE

E = I  de A

b = PrimerSimbolo de w

Fin Procedimiento

Funcion EsReconocidaCadena

Mientras ( b ≠ FinCadena ) AND  ( δ(E,b) ≠  nulo ) hacer

 	b = SiguienteSimbolo de w

Si   ( b ≠ FinCadena )   entonces    E = δ(E,b)     Finsi

 	FinMientras

Si   ( b = FinCadena )  AND ( (E,b)  = EstadoFinal )

entonces     Reconocida  =  TRUE

FinSi

retorna   Reconocida

Fin Funcion


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:


Lenguaje K-contextual
Siendo L un lenguaje regular, L será K-contextual si para cualquiera cadenas u1 v w1 , u2 v w2  L, con | v | = k, se verifica que:

TL(u1 ,v) = TL(u2 ,v).


Aceptor K-contextual

Si el lenguaje aceptado por el aceptor ( L(A) ) es un lenguaje k-contextual.