Existe um método conhecido para construir uma gramática, dado um conjunto finito de seqüências finitas?

Pela minha leitura, parece que a maioria das gramáticas está preocupada em gerar um número infinito de strings. E se você trabalhasse o contrário?

Se forem dadas n strings de m length, deve ser possível fazer uma gramática que gere essas strings, e apenas essas strings.

Existe um método conhecido para fazer isso? Idealmente, um nome de técnica que eu possa pesquisar. Como alternativa, como eu faria uma pesquisa na literatura para encontrar esse método?

Isso se enquadra no tópico geral da "indução gramatical"; pesquisar nessa frase irá gerar toneladas de literatura. Consulte, por exemplo, Induzindo uma gramática livre de contexto , https://en.wikipedia.org/wiki/Grammar_induction , https://cstheory.stackexchange.com/q/27347/5038 .

Para idiomas regulares (em vez de sem contexto), consulte também O regex golf NP-Complete? , Menor DFA que aceita seqüências de caracteres dadas e rejeita outras strings , existem melhorias no algoritmo de Dana Angluin para aprender conjuntos regulares e https://cstheory.stackexchange.com/q/1854/5038 .

Se o número de strings for finito, diga set você sempre pode criar uma gramática livre de contexto que gere todas essas strings, deixe A ser um terminal e, em seguida, a regra pode ser A → s 1 | s 2 | . . . s n . Para um conjunto finito de cadeias, você pode até criar um autômato de estado finito que aceita apenas essas cadeias. Portanto, o caso do conjunto finito de strings é realmente trivial.$S=\{s_1,s_2....s_m\}$$A$$A \to s_1|s_2|...s_n$

Existem várias maneiras, então você precisa impor critérios adicionais à qualidade dos resultados.

1. Lista: Para cada sequência no idioma, tenha uma regra S → w . Seja S o ponto inicial não-terminal. Feito.$w$$S \rightarrow w$$S$
2. $w$$X_w$$w_1xw_2$$x$$X_{w_1} \rightarrow xX_{w_2}$$w$$X_w \rightarrow \epsilon$$X_\epsilon$
3. Árvore de sufixo: a mesma, invertida.
4. A aplicação de um algoritmo garantido para produzir uma gramática de tamanho mínimo, por exemplo, com o número mínimo de regras. Eu não sei o quão difícil isso é.

O que você está perguntando é semelhante a um índice de pesquisa. Na verdade, os transdutores de estado finito podem ser criados e usados ​​para reconhecer o texto alimentado a eles. Por exemplo, Lucene usa este algoritmo: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698

Para um uso prático, confira este post de Andrew Gallant: Índice 1.600.000.000 de chaves com autômatos e ferrugem

No post, ele descreve um método para construir uma FSA, com um corpus de texto que reconhece todas as palavras. O resultado final é construir um FST aproximadamente mínimo a partir de chaves pré-classificadas em tempo linear e em memória constante.

A implementação está disponível em sua fstbiblioteca: https://github.com/BurntSushi/fst

Uma resposta para a pergunta feita pelo reinierpost que também responde à pergunta original:

Construímos o autômato de dicionário da seguinte maneira:

1. construa um autômato que leia e aceite exatamente a primeira string.
2. para a próxima sequência, comece a lê-la com o autômato até que, para alguma letra, não haja transição. inicie uma nova ramificação para o restante da string. repita até que todas as strings sejam processadas

O tamanho máximo do autômato é o comprimento total das cadeias de entrada. Supondo que você possa simular transições e criar novas em tempo constante, também o tempo de execução é o comprimento total das seqüências de entrada. Não há casos melhores ou piores.

Esse autômato é mínimo. Como no caso normal, autômatos e gramáticas correspondem quase um a um, o mesmo se aplica à gramática. É claro que é impossível construir algo de tamanho n em menos de n tempo.