La identificación de lenguaje en el límite es un modelo formal para la inferencia inductiva.
Fue presentado por E. Mark Gold en su artículo "Language identification in the limit".
[1] En este modelo, a un aprendiz se le proporciona una presentación (es decir, cadenas de caracteres) de algún lenguaje formal.
Cada vez que se lee un elemento de la presentación, el aprendiz debe proporcionar una representación (por ejemplo, una gramática formal) para el lenguaje.
Se dice que un aprendiz puede identificar en el límite una clase de lenguajes si, dada cualquier presentación de cualquier lenguaje en la clase, el aprendiz producirá solo un número finito de representaciones erróneas y, por lo tanto, convergerá a la representación correcta en un número finito de pasos, sin embargo, sin poder necesariamente anunciar su correctitud ya que, posteriormente, un contraejemplo de esa representación podría aparecer como un elemento.
En su artículo,[2] Gold introduce para contrastar los modelos más fuertes: Un modelo formal más débil es el Aprendizaje PAC, introducido por Leslie Valiant en 1984.
Si se requiere que un alumno sea eficaz, entonces se puede aprender una clase indizada de lenguajes recursivos en el límite si hay un procedimiento efectivo que enumere uniformemente las cadenas que caracteres que ocurren solo en un lenguaje para cada lenguaje de la clase (condición 1).
[7] No es difícil ver que si permitimos a un aprendiz ideal (es decir, una función arbitraria), entonces una clase indexada de lenguajes es aprendible en el límite si cada lenguaje en la clase tiene una cadena que caracteres que solo ocurre en ese lenguaje (condición 2).
En particular, la clase de lenguajes finitos es identificable en el límite por presentación por texto (cf.
Ejemplo 2 encima), mientras que la clase de los lenguajes regulares no lo es.
Esta es exactamente la Condición 3 en artículo de Angluin.
[10][11] Angluin mostró que si una clase de lenguajes recursivos tiene espesor finito, entonces es aprendible en el límite.
y cada secuencia infinita de lenguajes en la clase
, existe un número finito n tal que
[14] Está demostrado que una clase de lenguajes recursivamente enumerable se puede aprender en el límite si tiene elasticidad finita.