# Indução de linguagens regulares

Em teoria da aprendizagem computacional, indução de linguagens regulares refere-se à tarefa de obter a descrição formal (e.g. gramática) de uma linguagem regular a partir de um dado conjunto de exemplos de cadeias. Embora Mark E. Gold tenha mostrado que nem toda linguagem regular pode ser obtida dessa forma (veja identificação de linguagem no limite), abordagens têm sido investigadas para uma variedade de subclasses. Elas são esboçadas neste artigo. Para a obtenção de gramáticas mais gerais, veja indução de gramática.

## Exemplo

Uma linguagem regular é definida como um conjunto (finito ou infinito) de cadeias que pode ser descrito por um dos formalismos matemáticos chamados "autômato finito", "gramática regular", ou "expressão regular", onde todas eles têm o mesmo poder de expressão. Uma vez que as expressões regulares apresentam notações consideravelmente menores, elas serão introduzidas e utilizadas aqui. Dado um conjunto Σ de símbolos (também chamado de alfabeto), uma expressão regular pode ser
* ∅ (denotando o conjunto vazio de cadeias),
* ε (denotando o conjunto unitário contendo somente a cadeia vazia),
* a (onde a é qualquer caractere contido em Σ, denotando o conjunto unitário contento somente a cadeia com o caractere a),
* r+s (onde r e s são, por sua vez, expressões regulares, denotando o conjunto que representa a união entre r e s),
* r⋅s (denotando o conjunto de todas as possíveis concatenações entre cadeias dos conjuntos r e s),
* r$^+$ (denotando o conjunto de n concatenações repetidas entre cadeias do conjunto r, para qualquer n ≥ 1), ou
* r$^*$ (analogamente, denotando o conjunto de n concatenações repetidas, mas também incluindo a cadeia vazia, quando n é igual a 0).
Por exemplo, considerando Σ = { 0,1 }, a expressão regular (0+1+ε)⋅(0+1) denota o conjunto de todos os números binários com um ou dois dígitos (zeros à esquerda são permitidos) enquanto 1⋅(0+1)$^*$⋅0 denota o conjunto (infinito) de todos os números binários pares (zeros à esquerda não são permitidos).
Dado um conjunto de cadeias (também chamado de "exemplos positivos"), a tarefa de indução de linguagem regular é criar uma expressão regular que denota o conjunto contendo todas elas. Como um exemplo, dado { 1, 10, 100 }, uma descrição "natural" pode ser a expressão regular 1⋅0$^*$, correspondendo a caracterização informal "um 1 seguido arbitrariamente por muitos (talvez até nenhum) 0s". No entanto, (0+1)$^*$ e 1+(1⋅0)+(1⋅0⋅0) são outras expressões regulares, denotando o maior (assumindo Σ = {0,1}) e o menor conjunto contendo as cadeias dadas, chamados de generalização trivial superior e generalização trivial inferior, respectivamente. Algumas abordagens trabalham em uma configuração estendida onde um conjunto de "exemplos negativos" de cadeias também é dado; então, uma expressão regular pode ser encontrada para gerar todos os positivos, mas nenhum dos exemplos negativos.
* Reticulado de autômatos gerando as cadeias 1, 10, e 100 (exemplos positivos). Para cada um dos exemplos negativos de cadeias 11, 1001, 101, e 0, o segmento inicial dos autômatos gera como mostrado. O único autômato que gera todo o { 1, 10, 100}, mas nenhum do { 11, 1001, 101, 0 } são os autômatos triviais de baixo e o mais da direita da imagem, correspondendo a expressão regular 1⋅0$^*$.

## Reticulado de autômatos

Dupont et al. mostrou que o conjunto de todos os autômatos finitos estruturalmente completos gerando um dado conjunto de entrada de cadeias exemplo forma um reticulado, com o autômato trivial generalizado inferior e a generalização superior como o elemento de baixo e de cima, respectivamente. Cada membro do reticulado pode ser obtido pela fatoração do autômato generalizado inferior por uma relação de congruência apropriada. A imagem mostra um exemplo para o conjunto de cadeias de entrada { 1, 10, 100 }. Cada autômato é denotado por uma expressão regular equivalente. Para a generalização trivial inferior do nó de baixo da imagem, a forma do autômato também está esboçada em cinza, consistindo dos estados a, b, c, e d. Cada nó do autômato é o resultado da fatoração do autômato de baixo da imagem pela relação de congruência mostrada em cinza embaixo do nó.
Se ambos os exemplos positivos e negativos de cadeias são dados, Dupont et al. constrói o reticulado a partir dos exemplos positivos e então investiga a fronteira de separação entre os autômatos que geram os exemplos negativos e os que não geram. Os mais interessantes são os autômatos imediatamente abaixo da fronteira. Na imagem, as fronteiras de separação são mostradas para o exemplo negativo de cadeias 11, 1001, 101, 0.
Coste e Nicolas apresentam um método de busca próprio dentro deste reticulado, o qual é relacionado ao paradigma de aprendizagem versão espaço de Mitchell. Para encontrar a fronteira de separação, eles utilizam uma algoritmo de coloração de grafos no estado de relação de desigualdade induzido pelos exemplos negativos. Posteriormente, eles investigam uma série de relações de ordenação no conjunto de todos os possíveis estados de fusão.
Kudo e Shimbo usam a representação por fatoração de autômatos para criar um framework único para as seguintes abordagens (esboçadas abaixo):
* Linguagens k-reversíveis e a abordagem de "agrupamento de cauda",
* Autômato sucessor e o método antecessor-sucessor, e
* Abordagens baseadas em bombeamento (framework de integração contestado por Luzeaux, no entanto).
Cada uma dessas abordagens corresponde a um tipo particular de relação de congruência utilizada para fatoração.

## Abordagens
### Linguagens k-reversíveis

Angluin considera os chamados autômatos regulares "k-reversíveis", isto é, autômatos determinísticos os quais cada estado pode ser alcançado a partir de, no máximo, um estado, seguindo uma cadeia de transições de tamanho k. Formalmente, se Σ, Q, e δ denotam o alfabeto de entrada, o conjunto de estados e a função de transição de um autômato A, respectivamente, então A é chamado de k-reversível se: ∀a$_0$,...,a$_k$ ∈ Σ ∀s$_1$, s$_2$ ∈ Q: δ*(s$_1$,a$_0$...a$_k$) = δ*(s$_2$,a$_0$...a$_k$) ⇒ s$_1$ = s$_2$, onde δ* significa a extensão homomórfica de δ para palavras arbitrárias. Angluin apresenta um algoritmo cúbico para a obtenção da menor linguagem k-reversível para um dado conjunto de palavras de entrada; para k = 0, o algoritmo tem complexidade quase linear. A singularidade do estado requerido após k + 1 símbolos dados força a unificação dos estados do autômato, levando a uma generalização apropriada diferente do autômato trivial generalizado inferior. Esse algoritmo tem sido utilizado para aprender partes simples da sintaxe do inglês; posteriormente, uma versão incremental foi fornecida Outra abordagem baseada em autômatos k-reversíveis é o método de "agrupamento-cauda".

### Autômatos sucessores

A partir de um dado conjunto de cadeias de entrada, Vernadat e Richetin constroem o chamado autômato sucessor, consistindo de um estado para cada caractere distinto e uma transição entre cada dois estados de caracteres adjacentes. Por exemplo, o conjunto unitário de entrada { aabbaabb } conduz a um autômato correspondente a expressão regular (a$^+$⋅b$^+$)$^*$.
Uma extensão dessa abordagem é o método do antecessor-sucessor o qual generaliza cada repetição de caractere imediatamente em um fecho de Klenee e depois inclui para cada caractere o conjunto dos seus possíveis antecessores no seu estado. Autômatos sucessores podem expressar exatamente a classe das linguagens locais. Uma vez que cada linguagem regular é a imagem homomórfica de uma linguagem local, gramáticas de uma classe formadora pode ser obtida por levantamento, se um [[homomorfismo]] apropriado (dependendo da aplicação pretendida) é fornecido. Em particular, existe um homomorfismo para a classe das linguagens que podem ser obtidas pelo método do antecessor-sucessor. A aprendizibilidade das linguagens locais pode ser reduzida para as linguagens k-reversíveis.
* Derivação de Brzozowski (no fundo vermelho) de um dicionário de conjunto de cadeias relacionadas a "con"
* Ilustração do lema do bombeamento para autômatos regulares

### Abordagens iniciais

Chomsky e Miller (1957) usaram o lema do bombeamento: Eles "advinham" uma parte v de uma cadeia de entrada uvw e tentam construir um ciclo de correspondência no autômato a ser obtido; usando consultas de pertinência eles perguntam, para um k apropriado, qual das cadeias uw, uvvw, uvvvw, ..., uv$^k$w também pertence a linguagem a ser obtida, refinando dessa forma a estrutura do autômato. Em 1959, Solomonoff generalizou essa abordagem como gramáticas livre de contexto, a qual também obedece ao lema do bombeamento.

### Autômatos de cobertura

Câmpeanu et al. entende um autômato finito como uma representação compacta de uma linguagem grande e finita. Dado uma linguagem F, eles procuram pelo chamado autômato de cobertura A tal que a sua linguagem L(A) cubra F no seguinte sentido: L(A) ∩ Σ$^{≤l}$ = F, onde l é o tamanho da cadeia mais longa em F, e Σ$^{≤l}$ denota o conjunto de todas as cadeias que não são maiores que l. Se tal autômato de cobertura existe, F é unicamente determinado por A e l. Por exemplo, F = { ad, read, reread } tem l = 6 e um autômato de cobertura correspondendo a expressão regular (r⋅e)$^*$⋅a⋅d.
Para duas cadeias x e y, Câmpeanu et al. define x ~ y se xz∈F ⇔ yz∈F para qualquer cadeia z de tamanho tal que ambos xz e yz não são maiores que l. Baseado nessa relação, cuja falta de transitividade causa problemas técnicos consideráveis, eles fornecem um algoritmo O(n$^4$) para construir a partir de F um autômato de cobertura A com um número mínimo de estados. Além isso, para união, intersecção e diferença de duas linguagens finitas, eles fornecem operações correspondentes em seus autômatos de cobertura. Păun et al. melhorou a complexidade de tempo para O(n$^2$).

### Autômatos residuais

Para um conjunto S de cadeias e a cadeia u, a derivativa de Brzozowski u$^{−1}$S é definida como o conjunto de todo o restante de cadeias que podem ser obtidas a partir de uma cadeia em S tirando o prefixo u (se possível), formalmente: u$^{−1}$S = { v ∈ Σ$^*$: uv ∈ S }, conforme a imagem. Denis et al. define o autômato residual como um autômato finito não-determinístico A onde cada estado q corresponde a uma derivativa de Brzozowski da sua linguagem de aceitação L(A), formalmente: ∀q∈Q ∃u∈Σ$^*$: L(A,q) = u$^{−1}$L(A), onde L(A,q) denota a linguagem aceita a partir de q como estado inicial.
Eles mostram que cada linguagem regular é gerada por um único autômato residual mínimo. Seus estados são ∪-indecomponíveis derivativas de Brzozowski, e pode ser exponencialmente menor que o menor autômato determinístico. Além disso, eles mostram que o autômato residual para linguagens regulares pode ser obtido em tempo polinomial, mesmo assumindo amostras de entradas favoráveis. Eles forneceram o algoritmo de obtenção do autômato residual e provaram que pode-se obter o autômato pela sua amostra característica de entradas de cadeias positivas e negativas.

### Expressões regulares reduzidas

Brill define uma expressão regular reduzida como
* a (onde a é qualquer caractere em Σ; denotando o conjunto unitário contendo apenas a cadeia com o único caractere a),
* ¬a (denotando qualquer outro caractere individual em Σ exceto a),
* • (denotando qualquer caractere individual em Σ)
* a$^*$, (¬a)$^*$, ou •$^*$ (denotando arbitrariamente muitos, possivelmente zero, repetições de caracteres provenientes do conjunto de a, ¬a, ou •, respectivamente), ou
* r⋅s (onde r e s são, por sua vez, simplesmente expressões regulares reduzidas; denotando o conjunto de todas as possibilidades de concatenação de cadeias dos conjuntos r e s).
Dado um conjunto de cadeias de entrada, ele constrói passo a passo a árvore na qual cada ramo é nomeado por uma expressão regular reduzida aceitando um prefixo de algumas cadeias de entrada, e cada nó é nomeado com o conjunto de tamanho de prefixos aceitos. Ele objetiva a obtenção de regras de correção para os erros de grafia da língua inglesa, ao invés de considerações teóricas sobre a aprendizibilidade das classes de linguagem. Consequentemente, ele usa heurísticas para podar a árvore durante a construção, trazendo uma melhora de tempo de execução considerável.

## Aplicações

* Encontrando padrões comuns em descrições de estruturas de DNA e RNA (Bioinformática)
* Modelando aquisição da linguagem natural por humanos
* Obtendo descrições estruturais a partir de documentos estruturados de exemplo, em particular definição de tipo de documentos (DTD) a partir de documentos SGML
* Aprendendo a estrutura de composições musicais
* Obtendo representação compacta de linguagens finitas
* Classificando e recuperando documentos
* Gerando corretores de regras dependentes de contexto para erros gramaticais na língua inglesa