# Identificação de linguagem no limite

Identificação de linguagem no limite é um modelo formal de inferência indutiva. Esse modelo foi introduzido por E. Mark Gold no seu artigo com o mesmo título. Nesse modelo, um aprendiz é fornecido com a apresentação (i.e. strings) de alguma linguagem formal. A aprendizagem é vista como um processo infinito. Cada vez que um elemento da apresentação é lido, o aprendiz deve fornecer uma representação (e.g. uma gramática formal) para a linguagem. Um aprendiz pode identificar o limite de uma classe de linguagens se dada qualquer representação de qualquer linguagem da classe, o aprendiz irá produzir somente um número finito de representações erradas, e portanto, converge na representação correta em um número finito de passos, sem necessariamente ser capaz de dizer sua correção desde um contraexemplo para que a representação possa parecer um elemento arbitrariamente grande.
Gold definiu dois tipos de apresentações:
* Texto (informação positiva): uma enumeração de todas as palavras que a linguagem consiste;
* Representação completa (informação positiva e negativa): uma enumeração de todas as possíveis palavras, cada uma com um rótulo indicando se a palavra pertence à linguagem ou não.

## Capacidade de aprendizado

Este modelo é uma primeira tentativa de capturar formalmente a noção de capacidade de aprendizado. O artigo de Gold introduz para o contraste dos modelos mais fortes.
* Identificação finita(onde o aprendiz tem que dizer a correção depois de um número finito de passos), e
* Identificação em tempo fixo(onde a correção tem que ser alcançada depois de um número de passos especificado à priori.
Um modelo mais fraco de aprendizagem é o modelo aprendizagem provavelmente aproximadamente correto (PAC), introduzido por Leslie Valiant em 1984.

## Exemplos

Exemplo 4 :
| | Professor | Aprendizes | Aprendizes |
| | | Advinho | Questão |
| 0. | | | abab |
| 1. | yes | abab | baba |
| 2. | yes | a$^*$(ba)$^*$b$^*$ | aa |
| 3. | no | (ab)$^*$(ba)$^*$(ab)$^*$(ba)$^*$ | bababa |
| 4. | yes | (ab+ba)$^*$ | babb |
| 5. | no | (ab+ba)$^*$ | baaa |
Exemplo 3 :
| | Professor | Aprendiz |
| 1. | abab | abab |
| 2. | baba | a$^*$(ba)$^*$b$^*$ |
| 3. | aa | (ab)$^*$(ba)$^*$(ab)$^*$(ba)$^*$ |
| 4. | bababa | (ab+ba)$^*$ |
| 5. | babb | (ab+ba)$^*$ |
| 6. | baaa | (ab+ba)$^*$ |
| 7. | ε | (ab+ba)$^*$ |
Exemplo 2 :
| | Professor | Aprendiz |
| 1. | abab | abab |
| 2. | ba | abab+ba |
| 3. | baba | abab+ba+baba |
| 4. | ba | abab+ba+baba |
| 5. | baba | abab+ba+baba |
| 6. | abab | abab+ba+baba |
| 7. | ε | abab+ba+baba+ε |
Exemplo 1 :
| | Professor | Aprendiz |
| 1. | abab | abab |
| 2. | baba | abab+baba |
| 3. | baabab | (b+ε)(ab)$^*$ |
| 4. | baabab | (b+ε)(ab)$^*$+baabab |
| 5. | abbaabba | (ab)$^*$(ba)$^*$(ab)$^*$(ba)$^*$ |
| 6. | baabbaab | (ab+ba)$^*$ |
| 7. | bababa | (ab+ba)$^*$ |
É didático olhar para exemplos concretos de sessões de aprendizagem a definição de identificação no limite fala.
* Exemplo 1: Sessão fictícia para aprender uma linguagem regular L sobre o alfabeto {a,b} da apresentação do texto. Em cada passo o professor dá uma palavra pertencente a L, e o aprendiz advinha uma resposta para L, codificado como uma expressão regular. No 3º passo, o “palpite” do aprendiz não é consistente com a palavra vista até agora; no 4º passo, o professor dá uma palavra repetidamente. Depois do 6º passo, o aprendiz fica com a expressão regular (ab+ba)*. Se acontecer disso ser uma descrição de uma linguagem L o professor tem em mente, diz-se que o aprendiz aprendeu esta linguagem. Se um programa de computador para o papel do aprendiz existisse e fosse capaz de aprender com sucesso cada linguagem regular, esta classe de linguagens seria identificável no limite. Gold tem mostrado que esse não é o caso.
* Exemplo 2: Um algoritmo de aprendizagem particular sempre supondo L é apenas a união de duas palavras visto até agora. Se L é uma linguagem finita, o aprendiz vai, eventualmente, descobrir isso corretamente, contudo, sem ser capaz de dizer quando. Embora a descoberta não tenha mudado durante o passo 3 até o 6, o aprendiz não pode ter certeza se está correto. Gold tem mostrado que a classe de linguagens finitas são identificáveis no limite; no entanto, essa classe não é nem finita nem identificada em tempo fixo.
* Exemplo 3: Aprendizado de apresentação completa dita. Em cada passo, o professor dá uma palavra e diz se ela pertence a L (verde) ou não (vermelho, riscado). Cada possível palavra é eventualmente classificada nesta forma pelo professor.
* Exemplo 4: Aprendizado de apresentação completa por solicitação. O aprendiz dá uma palavra como consulta, o professor diz se essa pertence a L (sim) ou não (não); o aprendiz então dá um palpite para L, seguido pela próxima palavra de consulta. Neste exemplo, o aprendiz passa como consulta, em cada passo, somente a mesma palavra como dado pelo professor no exemplo 3. Em geral, Gold tem mostrado que cada classe de linguagem identificada na configuração “apresentação solicitada” é também identificada na configuração, “apresentação-dita”, uma vez que o aluno, em vez de consultar a palavra, só precisa esperar até esta ser, eventualmente, dada pelo professor.

## Caracterização de capacidade de aprendizagem

Dana Angluin deu as características de aprendizagem de texto (informação positiva) em 1980 em um artigo.
Se um aprendiz é necessário para ser eficaz, em seguida, uma classe indexada de linguagens recursivas é capaz de aprender no limite se existe um procedimento eficaz que uniformemente enumera tell-tales para cada linguagem na classe (condição 1). Isto não é difícil de ver, que se nós permitimos um aprendiz ideal (i.i, uma função arbitrária), então uma classe de linguagens indexadas são capaz de aprender no limite se cada linguagem na classe tem um tell-tale (condição 2).

## Classe de linguagens capazes de aprender no limite

Linhas divisórias entre classes de linguagens identificáveis e não-identificáveis :
| Modelo de capacidade de aprendizado | Classe de linguagens |
| Apresentação textual anômala ||
| | Recursivamente enumeráveis |
| | Conjunto recursivo |
| Apresentação Completa ||
| | Primitive recursive |
| | Sensível ao contexto |
| | Livres do contexto |
| | Regular |
| | Superfinita. |
| Apresentação de texto normal ||
| | Finita |
| | Única |
A tabela mostra quais classes de linguagens são identificadas no limite em quais modelos de aprendizagem. No lado direito, cada classe de linguagem é uma superclasse de todas classes menores. Cada modelo de aprendizagem(i.e. tipo de apresentação) pode identifica no limite todas as classes abaixo dela. Em particular, a classe de linguagens finitas são identificadas no limite por “apresentação de texto”(cf. Exemplo 2 acima), enquanto a classe de linguagens regulares não é.
Linguagens padrões (linguagem formal), introduzidas por Dana Angluin em outro artigo em 1980, são, também, identificáveis por apresentação textual normal; uma vez que eles estão acima das únicas (singleton) e abaixo da classe de linguagem primitiva recursiva, mas incomparável para as classes entre elas.

## Condições suficientes para aprendizado

Condição 1 no artigo de Angluin não é sempre fácil de verificar. Contudo, pessoas vêm com várias condições suficientes para a capacidade de aprendizado de uma classe de linguagens. Veja também indução de linguagens regulares para subclasses capacidade de aprendizado de linguagens regulares.

### Espessura finita

Uma classe de linguagens tem espessura finita se todo conjunto de palavras não-vazias está contido no maior número finito de linguagens da classe. Isso é exatamente a condição 3 no artigo de Angluin. Angluin mostrou que se uma classe de linguagens recursivas tem espessura finita, então ela é capaz de aprender no limite.
Uma classe com espessura finita certamente satisfaz condição-MEF e condição-MMF; em outras palavras, espessura finita implica espessura M-finita.

### Elasticidade finita

Uma classe de linguagens tem elasticidade finita se para toda sequencia infinita de palavras s$_0$, s$_1$,... e toda sequencia infinita de linguagens na classe L$_1$,L$_2$,..., existe um numero finito n tal que s$_n$ não pertence L$_n$ é inconsistente com {s$_1$, …, s$_{n-1}$}; isto mostra que a classe de linguagens recursivamente enumeráveis é capaz de aprender no limite se esta tem elasticidade finita.
Isto mostra que uma classe de linguagens recursivamente enumeráveis é capaz de aprende no limite se esta tem elasticidade finita.

## Ideia de limite de mudança

Um limite acima do número de mudança de hipóteses que ocorre antes da convergência.

## Outros conceitos
### Propriedade de cruzamento infinito

Uma linguagem L tem propriedade de cruzamento infinito dentro de uma classe de linguagens se existe uma sequência infinita Li de linguagens distintas em uma sequência de conjuntos finitos T$_i$ tal que:
* $T_{1}\subset T_{2}\subset ...$,
* $T_{i}\in L_{i}$,
* $T_{i+1}\not \in L_{i}$, e
* $\lim _{n=\infty }T_{i}=L$.
Note que L não é necessariamente um membro da classe de linguagem.
Não é difícil de ver que,se existe uma linguagem com propriedade de cruzamento infinito dentro da classe de linguagens, então esta classe de linguagens tem elasticidade infinita.

## Relações entre conceitos

* Espessura finita implica elasticidade finita; o inverso não é verdade.
* Elasticidade finita e capacidade de aprender conservadoramente implica na existência de um limite acima do número de mudanças. Contudo, espessura M-finita sozinha não implica na existência de uma "ideia de limite de mudança"; mas a existência de uma "ideia de limite de mudança" implica espessura M-finita.
* A existência de uma ideia de limite de mudança implica capacidade de aprendizado; o inverso não é verdade..
* Se não há ordem de acumulação para uma classe de linguagens, então existe uma linguagem (não necessariamente na classe) que tem a propriedade de cruzamento infinito dentro da classe, que por sua vez implica elasticidade infinita na classe.

## Questões abertas

* Se uma classe contável de linguagens recursivas tem uma “ideia de limite de mudança” para aprendizes não-computáveis, a classe também tem uma “ideia de limite de mudança” para aprendizes computáveis, ou a classe é incapaz de aprender por um aprendiz computável?