Según mi lectura, parece que la mayoría de las gramáticas se preocupan por generar un número infinito de cadenas. ¿Qué pasa si trabajas al revés?
Si se le dan n cadenas de m longitud, debería ser posible hacer una gramática que genere esas cadenas y solo esas cadenas.
¿Existe un método conocido para hacer esto? Idealmente, un nombre de técnica que pueda investigar. Alternativamente, ¿cómo podría hacer una búsqueda en la literatura para encontrar dicho método?
formal-languages
regular-languages
formal-grammars
finite-sets
Gustav Bertram
fuente
fuente
Respuestas:
Esto cae dentro del tema general de "inducción gramatical"; buscar esa frase arrojará toneladas de literatura. Consulte, por ejemplo, Inducir una gramática libre de contexto , https://en.wikipedia.org/wiki/Grammar_induction , https://cstheory.stackexchange.com/q/27347/5038 .
Para los idiomas normales (en lugar de los que no tienen contexto), consulte también ¿Es regex golf NP-Complete? , DFA más pequeño que acepta cadenas dadas y rechaza otras cadenas dadas , ¿Hay mejoras en el algoritmo de Dana Angluin para aprender conjuntos regulares y https://cstheory.stackexchange.com/q/1854/5038 ?
fuente
Si el número de cadenas es finito, diga el conjunto siempre puedes encontrar una gramática libre de contexto que genere todas esas cadenas, deja que A sea no terminal, entonces la regla puede ser A → s 1 | s 2 | . . . s n . Para un conjunto finito de cadenas, incluso puede crear un autómata de estado finito que acepte solo esas cadenas. Entonces, el caso de un conjunto finito de cadenas es realmente trivial.S= { s1, s2. . . . smetro} UNA A → s1El | s2El | . . . snorte
fuente
Hay muchas formas, por lo que debe imponer criterios adicionales sobre la calidad de los resultados.
fuente
Lo que está preguntando es similar a un índice de búsqueda. De hecho, se pueden crear y utilizar transductores de estado finito para reconocer el texto que se les envía. Por ejemplo, Lucene utiliza este algoritmo: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698
Para un uso práctico, consulte esta publicación de blog de Andrew Gallant: indexe 1,600,000,000 de claves con autómatas y óxido
En la publicación, describe un método para construir una FSA dado un corpus de texto de modo que reconozca todas las palabras. El resultado final es construir un FST aproximadamente mínimo a partir de claves previamente ordenadas en tiempo lineal y en memoria constante.
La implementación está disponible en su
fst
biblioteca: https://github.com/BurntSushi/fstfuente
Una respuesta a la pregunta planteada por reinierpost que también responde a la pregunta original:
Construimos el autómata del diccionario de la siguiente manera:
El tamaño máximo del autómata es la longitud total de las cadenas de entrada. Suponiendo que puede simular transiciones y crear nuevas en tiempo constante, también el tiempo de ejecución es la longitud total de las cadenas de entrada. No hay mejores o peores casos.
Este autómata es mínimo. dado que en el caso regular los autómatas y las gramáticas corresponden casi uno a uno, lo mismo es cierto para la gramática. Por supuesto, es imposible construir algo de tamaño n en menos de n tiempo.
fuente