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


Uso de Informacion Semantica
Uso de Información Semántica

Introducción

Definiciones generales

Lemas

Algoritmos


Introduccion
Introducción

Ningún algoritmo puede identificar un conjunto completo de lenguajes regulares partiendo solamente de una muestra de ejemplos positivos. Por eso se usan algoritmos que utilizan una muestra positiva y otra información adicional. Normalmente esta información es suficiente para permitir una identificación en el límite. Esta información adicional puede ser el valor k, los ejemplos negativos, ...

Un tipo de información adicional se denomina Información semántica y se añade a los ejemplos positivos utilizando pares de situación/acción.


Definiciones Generales

Expresión general de máquina Mealy

Máquina Mealy destacadamente terminal

Máquina Mealy determinística

Generación de sucesión de pares

Muestra positiva de un lenguaje de situación/acción


Maquina Mealy
Expresión General de Máquina Mealy

Sextupla  (Q, X, Y, δ, I, F), donde:

Q    Conjunto finito de estados.

X     Conjunto de situaciones.

Y    Conjunto de acciones.

δ     Función de transición definida:

δ : Q ×  X   ——→  Y × Q

    	     (q , x)     →       δ (q , x) = (y , q')

I    Conjunto de estados iniciales.

F   Conjunto de estados finales.


Maquina Mealy Terminal
Solamente tiene un estado final


Maquina Mealy Tao-terminal
Tiene uno o varios estados termnales sin salidas y todos los arcos que acceden a ellos están etiquetados por la preja especial xτ /yτ.


Maquina Mealy Destacadamente Terminal
Máquina Mealy Destacadamente Terminal

Es a la vez terminal y τ-terminal.


Maquina Mealy Deterministica
Máquina Mealy Determinística

Si se cumple:

1)  ∀ q ∈ Q  y ∀ x ∈ X,  si δ ( q, x ) = ( y, q' )  entonces no existe otros q'' ∈ Q e y' ∈ Y , 	tales que  δ (q, x)=( y', q'' )

2)  | I | = 1, es decir, el conjunto de estados iniciales contiene un solo miembro.


Universo de Pares situación/accion
Σsa = (X × Y), siendo X el universo de símbolos de situación e Y el universo de símbolos de acción.

Se denomina Universo de pares situación/acción.


Generacion de Sucesion de Pares
Generación de Sucesión de Pares

Una máquina Mealy terminal se dice que genera la sucesión de pares:

(x1, y1) (x2, y2) ...... (xn, yn), sii, existe una sucesión de estados, no necesariamente distintos, q0, q1, q2, ....., qn , tales que:

(yi+1, qi+1)  ∈  δ(qi,xi+1) con  0 ≤ i ≤ (n-1), q0 ∈ I  y  qn ∈ F


Lenguaje de situacion/accion
Lsa = Conjunto de sucesiones de pares situación/acción.

se denomina Lenguaje de situación/acción.


Muestra Positiva de un Lenguaje de S/A
Muestra Positiva de un Lenguaje de Situación/Acción

Se denota por Ssa+.  es un subconjunto de Lsa.


Lemas

Lema 1. Biyección hb

Lema 2. Biyección ha

Lema 3. Biyección hu

Lema 4. Biyección hs+


Lema 1. Biyeccion hb
Lema 1. Biyección hb

Existe una biyección hb entre pares ( situación , acción ) y símbolos de un cierto alfabeto.

hb : Σsa  ←——→ Σ

     (s,a)	     →    s.a


Lema 2. Biyeccion ha
Lema 2. Biyección ha

Dada la biyección hb se puede establecer una biyección entre máquinas Mealy terminales y autómatas de estados finitos que denotaremos por ha .

Ejemplo:


Lema 3. Biyeccion hu
Lema 3. Biyección hu

Dada la biyección hb existe una biyección hu que aplica sucesiones de situación /acción  en cadenas de Σ.

hu :  Σsa* ←————————→   Σ*

     (s1a1)(s2a2)(s3a3) 	→	s1a1s2a2s3a3


Lema 4. Biyeccion hs
Lema 4. Biyección hs+

Dada la biyección hu, a partir de ella se define otra biyección hs+ que aplica sucesiones de lleva subconjuntos de sucesiones situación /acción  en cadenas.

hs+ :  P(Σsa*) ←————————→  P( Σ*)

    { (s1a1)(s2a2)(s3a3) }	→	{ s1a1s2a2s3a3 }

Todos los lemas permiten obtener un autómata finito a partir de una máquina Mealy y operar sobre él y después hacer el paso inverso para ajustar los resultados a una máquina Mealy.

                       hs+	                    1/hs+

Ssa+ ——→ S+ ——→ L ——→ Lsa


Algoritmos

SKR

SKC


SKR

•	Descripción

Parte de una muestra Ssa+, por medio de hs+ la transforma en S+ sobre el alfabeto.

Trabaja con máquinas Mealy destacadamente terminales.

•	Pasos del algoritmo

1. Aplicación  del algoritmo de inducción KR comenzando con k = 0.

2. Incrementar sucesivamente la k hasta obtener un aceptor de estado finito A sobre, tal 	que, 1/hu(A) corresponda a una máquina de Mealy determinística.

3. Si k superior a la longitud de la mayor de las cadenas de S+, devolver fallo.

•	Pseudocódigo

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

Entrada:  Ssa+, Muestra positiva de situación/acción no vacía.

Salida:	  Mf    Máquina Mealy mínima k-reversible determinística.

  f  ( valor final de k )  si la Maquina Mealy es determinística.

  FALLO  si la Maquina Mealy no es determinística.

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

Procedimiento INICIALIZAR

k = 0

S+ = hs+(Ssa+)

Fin Procedimiento

Funcion RESULTADO

Mientras  ( k ≤ ( máx (longitud de secuencia en Ssa+) ) )

AND

    ( Mk No determinística )    hacer

Ak = KR( S+, k )

Mk = 1/ha( Ak )

Si  Mk  No determinística  entonces  k = k + 1  Finsi 	FinMientras

Si    Mk  No determinística    entonces     retorna FALLO

       sino

retorna  f = k

retorna ( Mf, f )

FinSi

Fin Funcion


SKC

•	Descripción

Parte de una muestra Ssa+, por medio de hs+ la transforma en S+ sobre el alfabeto.

•	Pasos del algoritmo

1. Aplicación  del algoritmo de inducción KC comenzando con k = 0.

2. Incrementar sucesivamente la k hasta obtener un aceptor de estado finito A sobre, tal 	que, 1/hu(A) corresponda a una máquina de Mealy determinística.

3. Si k superior a la longitud de la mayor de las cadenas de S+, devolver fallo.

•	Pseudocódigo

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

Entrada:  Ssa+, Muestra positiva de situación/acción no vacía.

Salida:	  Mf    Máquina Mealy mínima determinística.

  f  ( valor final de k )  si la Maquina Mealy es determinística.

  FALLO  si la Maquina Mealy no es determinística.

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

Procedimiento INICIALIZAR

k = 0

S+ = hs+(Ssa+)

Fin Procedimiento

Funcion RESULTADO

Mientras  ( k ≤ ( máx (longitud de secuencia en Ssa+) ) )

AND

    ( Mk No determinística )    hacer

Ak = KC( S+, k )

Mk = 1/ha( Ak )

Si  Mk  No determinística  entonces  k = k + 1  Finsi 	FinMientras

Si    Mk  No determinística    entonces     retorna FALLO

       sino

 retorna  f = k

 retorna ( Mf, f )

FinSi

Fin Funcion