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


Definiciones

Definiciones Generales

Definiciones sobre Autómatas


Definiciones Generales

Conjunto de prefijos de un lenguaje L

Conjunto de sufijos de un lenguaje L

Conjunto de sufijos de longitud k

Muestra positiva

Muestra característica

Partición

Bloque

Refinamiento


Prefijos
Pr(L) = { u : ∃ v  ∈ Σ *  ∧  uv  ∈  L }

Σ * ⇒ Conjunto de cadenas de cualquier longitud que pueden formarse por concatenación de elementos del alfabeto , incluida la cadena vacía que se representa por λ .


Sufijos
TL(u) = { v : uv ∈ L }


Sufijos de longitud K
TkL(u) = { v : uv ∈ L  ∧  | v | ≤ k}


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


Muestra Caracteristica
S+ muestra característica de un cierto lenguaje L, si éste es el menor lenguaje que contiene a S+.


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

 Πs = { Si } i ∈ I , tal que, se cumple:

i )  ∪ Si = S ,  i ∈ I	y        ii )  Sr ∩ Ss = ∅,   ∀ r,s ∈ I, r ≠ s


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

Las aplicaciones se harán para s = estado.

Gráficamente:


Refinamiento
Πs = { Si } i ∈ I  es un refinamiento de Πs´ = { Sj´}  j ∈ J , si y sóo si,

∀ S´ ∈ Πs´ ,  S´ =  ∪Sh  con  h ∈ H  y  h ⊂ I

Es decir, cada bloque de Πs´ coincide con una partición de bloques de Πs.

Gráficamente:


Definiciones sobre Automatas
Definiciones sobre Autómatas

Expresión general

Función de transición generalizada

Autómata o Aceptor de prefijos

Autómata Cociente

Autómata Mínimo

Reconocimiento de una cadena


Expresion General
Expresión General de un Autómata Finito

Un autómata, que denotaremos por A, viene determinado por una quintupla del siguiente tipo:

 	A = ( Q, Σ, δ, I, F ), donde,

Q  representa al Conjunto de Estados (finito)

Σ  representa al Alfabeto.

δ  representa la Función de Transición

Si el autómata finito es determinístico (AFD):

 	δ  : Q × Σ ———→  Q

    	     (q , x)      →      δ (q, x)

Si el autómata finito es no determinístico (AFND):

δ : Q × Σ  ———→ P(Q)

                  	    (q , x)      →       δ (q , x) = {...,qi,...} ∈ P(Q)

I    representa al Estado Inicial

F   representa el conjunto de Estados finales o aceptores

A los autómatas finitos se les suele denominar también aceptores o reconocedores.

Representaremos como L(A) al lenguaje aceptado o reconocido por el autómata A.


Funcion de Transicion
Función de Transición Generalizada

•	Si el autómata finito es determinístico (AFD):   δ*  : Q × Σ* ———→  Q

 i) δ* (q , λ) = q

ii) δ* (q , wx) = δ (δ* (q, w),x)

La función de transición δ, es determinística, es decir no presenta ambigüedades en las transiciones de estados para una cierta entrada.

•	Si el autómata finito es no determinístico (AFND):  δ* : Q × Σ* ——→ P(Q)

i) δ* (q , λ) = q

           ii) δ* (q , wx) = ∪ δ (q', x) q'  ∈  δ* (q,w)

Es decir, dada una entrada en un cierto estado q, se puede pasar a distintos estados.

Para todo AFND se puede construir un AFD, de tal forma que el lenguaje reconocido por ambos autómatas coincida.


Automata Aceptor de Prefijos
Árbol (Autómata) Aceptor de Prefijos de una Muestra Positiva

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+


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.


Automata Minimo
Autómata Mínimo

Es un caso particular de autómata cociente.

Sea M = ( Q,Σ, δ, I, F ) un autómata finito deteminístico, el autómata mínimo que 	reconozca el mismo lenguaje que M será el autómata cociente:

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

donde Π está definida como sigue:

∀ qi, qj ∈ Q : B(qi, Π ) = B(qj, Π )   ⇔   (δ*(qi, w) ∈ F  ⇔   δ*(qj, w) ∈ F) , ∀ w ∈ Σ*


Reconocimiento de una Cadena

Cuando un autómata procesa una cadena y llega a un estado final a través de sucesivas transiciones, se dice que ha reconocido la cadena de entrada, es decir, que dicha cadena  pertenece al lenguaje reconocido por el autómata.


Ejemplo 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:


Introduccion
Introducción a la Inducción Gramatical

Inducción gramatical

Tipos de algoritmos

Ejemplo


Induccion Gramatical
¿Qué es la Inducción Gramatical?

Ejemplo

El problema de la inducción gramatical consiste en inducir una gramática o lenguaje a partir de una muestra finita de cadenas. El alcance de este resumen queda restringido a los lenguajes regulares. Para ello se utiliza como apoyo los autómatas finitos, y como fundamento el teorema que asegura igual capacidad computacional para gramáticas regulares y autómatas finitos:

"Para todo autómata finito, existe una gramática regular y una expresión regular tales que el lenguaje generado por la gramática y el representado por la expresión regular coincide con el lenguaje reconocido por el autómata finito."

Existen técnicas algorítmicas que permiten construir autómatas finitos partiendo de la información que proporciona una muestra de ejemplos y, en algunos casos, de información añadida: valores de parámetros, ejemplos negativos, etc. Estas técnicas se basan en lo que se conoce como inducción gramatical y su desarrollo es el objetivo de esta documentación.

Se verán diferentes tipos de algoritmos que infieren un lenguaje regular a partir de un subconjunto del mismo.


Tipos de Algoritmos

Los tipos de algoritmos que pueden inferir un cierto lenguaje se dividen en:

•	Algoritmos incrementales, en los cuales se introducen los ejemplos uno a uno; con los primeros ejemplos se obtiene una primera aproximación del autómata, con el siguiente ejemplo añadido se modifica el autómata anterior, sólo si es necesario, para que éste reconozca a la nueva cadena y así sucesivamente con todos los ejemplos que se añadan. Si a partir de un cierto ejemplo los siguientes ya no modifican el autómata se dice que el lenguaje es límite.

•	Algoritmos  no incrementales, en este caso, la inducción se realiza con la muestra completa y un ejemplo nuevo añadido supone volver a construir un nuevo autómata con la muestra incrementada en ese ejemplo.


Ejemplo Induccion
Ejemplo Inducción Gramatical

Partiendo de una muestra positiva  S+ = {aabb, ab, aab, abbb},	el problema que nos ocupa consistiría en inducir la gramática o autómata que genere un lenguaje regular englobando la muestra y para el que la muestra resulte representativa.

En este caso la gramática podría ser a+ b+, o bien, aa* bb*

La solución no tiene por que ser única.


Muestra Positiva
Se denotará por  S+  al conjunto de ejemplos positivos; es decir,

cadenas que pertenecen al lenguaje, llamado también muestra positiva.


Muestra Negativa
Se denotará por  S-  al conjunto de ejemplos negativos; es decir,

cadenas que no pertenecen al lenguaje, llamado también muestra negativa.


Significado signos
El símbolo  ∗  indica que ese carácter puede aparecer de 0 a n veces.

  	El símbolo  +  indica que ese carácter debe aparecer al menos una vez.


Lenguaje Regular
Se dice que un lenguaje, que denotaremos por L, es regular si existe un autómata finito, (o equivalentemente una gramática regular, o una expresión regular) que lo defina.


Otras Definiciones

Partición sobre un lenguaje

Partición sobre un conjunto de estados

Subaceptor de un autómata finito

Isomorfismo.Lema

Autómata finito determinístico k-ulterior

Autómata invertido

Autómata k-reversible

Lenguaje k-reversible

Aceptor destacadamente terminal

Aceptor ku-reversible

Aceptor k-contextual


Particion sobre un Lenguaje
Partición sobre un Lenguaje

ΠL sobre el conjunto de prefijos del lenguaje L, se define como:

 ∀ u,v  ∈ L   B(u, Π) = B(v, Π) ⇔  TL(u) = TL(v)


Particion sobre un Conjunto de Estados
Partición 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)


Subaceptor de Automata Finito
Subaceptor de Autómata Finito

A' es un subaceptor de A ⇔ L(A') ⊂ L(A),

es decir, el lenguaje reconocido por el también autómata finito A' → L(A'), está contenido o reconocido por un lenguaje de  A.


Isomorfismo. Lema

Todos los algoritmos de inducción que parten del árbol aceptor de prefijos se basan indirectamente en esta proposición.

Sea

L un lenguaje,

S+ una muestra positiva de L,

A0 un aceptor de prefijos de S+  = PT(S+), y

ΠPr(s+)  una restricción de ΠL a Pr(S+) entonces

A0 /ΠPr(s+) es isomorfo a un subaceptor de L, es decir, el lenguaje aceptado por ese autómata está contenido en L, es decir:

L ( A0 /ΠPr(s+)  ) ⊂  L


AFD k-ulterior
Autómata Finito Determinístico k-ulterior

Un autómata finito M se dice que es determinístico K-ulterior, si para dos estados q1, q2 que sean bien iniciales bien que exista un q3 y una x ∈ Σ  con δ(q3,x) = q1 y δ(q3,x) = q2, entonces no existe una cadena u ∈ Σ* de longitud k saliente de ellos. Es decir, que no se den ninguna de las situaciones que se muestran en el siguiente gráfico:


Automata Invertido
Autómata Invertido

Ar = ( Q, Σ, δr, I', F' ), siendo A = ( Q, Σ, δ, I, F ) un autómata finito deteminístico, donde:

δr : Q ——→  P( Q )  ,	será no determinístico,

δr(q,x) = {q' ∈ Q / δ(q',x) = q}

I'   Conjunto de estados iniciales = F

(siempre existe un autómata equivalente con un solo estado inicial)

F'  Conjunto de estados finales = { I }

Por ejemplo:


Automata K reversible
Autómata K-reversible

Si A es determinístico y Ar es determinístico en exploración k-ulterior.


Lenguaje k reversible
Lenguaje K-Reversible

Si existe un autómata k-reversible que lo reconozca.


Aceptor Tao-Terminal
Si existe un símbolo τ ∈ Σ   tal que:

δ(q,x) ∈ F , si y sólo si,   x = τ

Es decir que todos los arcos incidentes en estados terminales están etiquetados con τ.


Aceptor de Estado Objetivo
Si el autómata posee un único estado final y además de él no parte ninguna transición ni bucle.


Aceptor Destacadamente Terminal

Si es τ-terminal y aceptor de estado objetivo. Es decir, que sólo tiene un estado final (sin bucles) y todas las flechas hacia él están etiquetadas con el mismo símbolo τ.

Existe una biyección hτ que asocia a un aceptor A un aceptor destacadamente terminal hτ(A), tal que si L es el lenguaje reconocido por A entonces L (hτ(A)) = L . { τ }. Se supone que τ no pertenece a L.


Aceptor KU-reversible

Si el aceptor es destacadamente terminal y 1/hτ(A) es k-reversible.


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.


KR

•	Descripción

Dada una muestra devuelve un autómata KU-reversible que reconoce un lenguaje que incluye S+ .

El resultado final es normalizado para conseguir un autómata K-reversible usando 1/hτ.

•	Pasos del algoritmo

1. Partiendo de S+ creación de S0+ . Consiste en concatenar τ a todos los ejemplos por detrás.

 S0+  = S+ .  { τ }

 Σ0   = Σ ∪  { τ }	, será el nuevo alfabeto.

2. Construcción del autómata aceptor de prefijos PT(S0+)

3. Aunar estados finales. hτ ( PT (S0+) )

Los tres primeros pasos corresponden a la conversión del autómata en destacadamente terminal.

4. Cálculo del autómata con la χ de Angluin, es decir,

χ(u,v) =1, sii, u, v  transgreden las condiciones de KU-reversibilidad, en sucesivos pasos.

Gráficamente, se juntarán aquellos estados (u,v) que estén en alguna de las siguientes situaciones:

5. Cálculo de 1/hτ

•	Pseudocódigo

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

Entrada:      S+  Muestra positiva no vacía.

       k    Parámetro.

Salida:        A    Autómata finito K-reversible.

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

Procedimiento INICIALIZAR

S0+ = S+.  {τ}

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

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

LISTA = vacio

ParaCada  ( b ∈ Σ0 ) y  ( q ∈ Q0 ) hacer

 	 s ( {q}, b ) = δ0 (q, b)

 p ( {q}, b ) = δr0 (q, b)

FinPara

Elegir algún q' ∈ F0

ParaCada   q ∈  F0 - {q'}    hacer

 	InsertarPar( LISTA, (q', q ) )

FinPara

i = 0

Fin procedimiento

Procedimiento JUNTAR

Mientras  LISTA ≠ vacío  hacer

borrar elemento (q1, q2) de LISTA

B1 = B (q1 , Πi  )

B2 = B (q2 , Πi  )

Si   B1 ≠ B2   entonces

B3 =  B1 ≡  B2

Πi+1  = Πi  - B1 - B2 + B3

ParaCada  b ∈ Σ0  hacer

ActualizarFuncion-S ( B1,B2, B3, b)

ActualizarFuncion-P (B1,B2, B3, b, k)

FinPara

i = i + 1

FinSi

FinMientras

f  =  i

retorna  1/hτ (A0 / Πf )

Fin Procedimiento


KR Version Incremental
KR Versión Incremental

•	Pasos del Algoritmo

Sea S+ una muestra positiva y A el autómata obtenido como salida del algoritmo KR para esa muestra. Para la obtención del autómata inducido por KR 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. Concatenar w con τ y convertir A en destacadamente terminal, si no lo fuese.

3. 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 KR sobre el autómata resultante del paso 3.

•	Pseudocódigo

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

Entradas:      w  Cadena.

Salida:          A    Autómata finito KU-reversible.

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

Procedimiento INICIALIZAR

w0 = w . {τ}

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 KR

FinSi

Fin Procedimiento


KR Version con Ejemplos Negativos
KR 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 KR 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 KR 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


Actualizar Funcion-S
Procedimiento Actualizar Función-S

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

Entradas:      B1,B2, B3  bloques.

           b ∈ Σ0, un símbolo

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

Procedimiento ActualizarFuncion-S

Si   ( s ( B1, b )  AND s ( B2, b ) )  ≠  nulo   entonces

InsertarPar (  LISTA, (s ( B1, b ), s ( B2, b ) )  )

FinSi

Si    s ( B1, b )  ≠  nulo    entonces    s ( B3, b ) = s ( B1, b )

         sino           s ( B3, b ) = s ( B2, b )

FinSi

Fin Procedimiento


Actualizar Funcion-P
Procedimiento Actualizar Función-P

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

Entradas:     B1,B2, B3  bloques.

       b ∈ Σ0 , símbolo.

       k  parámetro.

Procedimiento ActualizarFuncion_P

ParaCada  q1 ∈  p ( B1,b )  y  q2 ∈  p ( B2,b )   hacer

Si   TienenPrefijoComun (q1, q2, Πi, k)  entonces 	InsertarPar( LISTA , (q1 , q2 ) )

FinSi

FinPara

p (B3, b)  =  p (B1, b)   ∪   p (B2, b)

Fin Procedimiento


Funcion PrefijoComun
Función TienenPrefijoComun

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

Entradas:      q1 , q2   estados.

        Πi   partición actual.

Salida:	        valor booleano.

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

Funcion TienenPrefijoComun

q1 →  B ( u1v1, Πi  )

q2  → B ( u2v2, Πi  )      con   u1v1 , u2v2  ∈  Pr(S+)

Si   ( | v1 | = k = | v2 | )  AND  ( v1  = v2 )   entonces      retorna VERDADERO

                                                 sino             retorna FALSO

FinSi

Fin Funcion


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.


Automata KU reversible
Aceptor KU-reversible

Si el aceptor es destacamente terminal y 1/hτ(A) es k-reversible.


Automata k-reversible
Autómata K-reversible

Si A es determinístico y Ar es determinístico en exploración k-ulterior.


Automata K-ulterior
Autómata Finito Determinístico k-ulterior

Un autómata finito M se dice que es determinístico K-ulterior, si para dos estados q1, q2 que sean bien iniciales bien que exista un q3 y una x ∈ Σ  con δ(q3,x) = q1 y δ(q3,x) = q2, entonces no existe una cadena u ∈ Σ* de longitud k saliente de ellos. Es decir, que no se den ninguna de las situaciones que se muestran en el siguiente gráfico:


Automata Tao-Terminal
Si existe un símbolo τ ∈ Σ   tal que:

δ(q,x) ∈ F , si y sóo si,   x = τ


Aceptor de Estado Objetivo
Si el autómata posee un único estado final y además de él no parte ninguna transición ni bucle.


Automata Destacadamente Terminal
Aceptor Destacadamente Terminal

Si es τ-terminal y aceptor de estado objetivo. Es decir, que sóo tiene un estado final (sin bucles) y todas las flechas hacia él están etiquetadas con el mismo símbolo τ.

Existe una biyección hτ que asocia a un aceptor A un aceptor destacadamente terminal hτ(A), tal que si L es el lenguaje reconocido por A entonces L (hτ(A)) = L . { τ }. Se supone que τ no pertenece a L.


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:


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.


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


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:


Bibliografía

Libros

Artículos


Libros

Hanson S.J., Remmele W., Rivest R.L. (Eds.). Machine Learning: From Theory to Applications. Springer-Verlag, 1993

 Hopcroft John E., Ullman Jeffrey D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979

 Muggleton Stephen. Inductive Acquisition of Expert Knowledge. Ed. Addison-Wesley, 1993

 Simon Herbert A. Autonomous Learning from the Enviroment. Wei-Min Shen, 1994


Articulos
Artículos

Angluin Dana. Inference of Reversible Languages. Journal of the Association for Computing Machinery, vol. 29, nº 3, Julio 1982, pp. 741-765

Angluin Dana, Smith Carl H. Inductive Inference: Theory and Methods. Computing Surveys, vol. 15, nº 3, Septiembre 1983, pp. 237-269

Gold E. Mark. Language Identification in the Limit. Information and Control 10, 1967, pp. 447-474

King-Sun Fu, Taylor L. Booth. Gramatical Inference: Introduction and Survey. Part I. IEEE Transactions on System, Man and Cybernetics, vol. SMC-5, nº, Enero 1975, pp. 95-110

Levine Barry. The Use of Tree Derivates and Sample Support Parameter for Inferring Tree Systems. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-4, nº, Enero 1982, pp. 25-34