¿Existe un método conocido para construir una gramática dado un conjunto finito de cadenas finitas?

10

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?

Gustav Bertram
fuente
55
Trivial: Construye la tabla BNF de las cadenas.
Joshua
Las cadenas son finitas por definición. Y no se puede "dar" un conjunto infinito a menos que tenga una descripción finita de él.
vonbrand

Respuestas:

11

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 ?

DW
fuente
Inducir gramáticas para lenguajes regulares posiblemente infinitos es difícil y bastante diferente de este problema.
reinierpost
Estoy marcando esta pregunta correcta, porque aunque no responde directamente a la pregunta (que resulta que es trivialmente solucionable como se indicó), me proporciona el tipo de terminología que necesito para investigar más.
Gustav Bertram
8

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}UNAUNAs1El |s2El |...snorte

Sashas
fuente
Creo que necesito revisar mi libro de texto de análisis. En retrospectiva, esta respuesta parece obvia. ¡Gracias!
Gustav Bertram
3

Hay muchas formas, por lo que debe imponer criterios adicionales sobre la calidad de los resultados.

  1. Lista: Para cada cadena en el idioma, tenga una regla S w . Deje S ser el no terminal inicial. Hecho.wSwS
  2. wXww1Xw2XXw1XXw2wXwϵXϵ
  3. Árbol de sufijo: el mismo, invertido.
  4. Aplicando un algoritmo garantizado para producir una gramática de tamaño mínimo, por ejemplo, con el número mínimo de reglas. No sé lo difícil que es esto.
reinierpost
fuente
Sí, después de la primera respuesta era obvio que debería haber impuesto criterios adicionales, pero me pareció injusto cambiar la pregunta después de la primera respuesta.
Gustav Bertram
Aún así, me encantaría saber la complejidad temporal de encontrar una gramática mínima para un conjunto finito determinado de cadenas ... digamos, en la longitud total de las cadenas o en la longitud total del resultado.
reinierpost
3

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.

FSA compartiendo prefijos y sufijos

La implementación está disponible en su fstbiblioteca: https://github.com/BurntSushi/fst

lkraider
fuente
1

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:

  1. construya un autómata que lea y acepte exactamente la primera cadena.
  2. para la siguiente cadena, comience a leerla con el autómata hasta que en alguna letra no haya transición. comenzar una nueva rama para el resto de la cadena. repita hasta que se procesen todas las cadenas

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.

Peter Leupold
fuente
Gracias. En cuanto a responder esta pregunta: no veo lo que esto contribuye sobre el reinicio. Además, no queremos respuestas que respondan o comenten otra respuesta: este no es un foro de discusión. La forma de hacerlo sería publicar una nueva pregunta y luego responderla usted mismo. Me doy cuenta de que eso podría no ser obvio. [Dicho esto, no veo cómo su respuesta responde al problema sobre el que reinierpost tenía curiosidad. El problema al final de la respuesta de reinierpost fue encontrar una gramática con el número mínimo de reglas. Su respuesta muestra cómo construir un DFA con un número mínimo de estados. (continuación)
DW
1
Por supuesto, podemos convertir ese DFA en una gramática regular, pero ¿qué te hace pensar que será mínimo en términos de la cantidad de reglas en la gramática? Parece que eso necesita una prueba.]
DW
Creo que mi respuesta es el tiempo de ejecución. Tienes razón, varias cosas que digo necesitarían alguna prueba. Pero la correspondencia entre las transiciones de Autómatas finitos y las reglas de Gramática regular es muy clara para mí (si esta última solo puede generar un terminal por regla como en la mayoría de las definiciones); entonces cualquier gramática más pequeña que la mía daría un autómata más pequeño que el mínimo. Así que creo que la gramática del autómata mínimo (no pruebo que la mía es mínima) también será mínima. - Tendré en cuenta su consejo sobre las respuestas, gracias
Peter Leupold
La noción de minimidad para DFA es con respecto al número de estados . ¿Esto implica minimidad con respecto al número de transiciones en el DFA, o minimización del número de reglas en la gramática resultante? Creo que tenemos que hacer un seguimiento de cuál es su métrica, ya que de lo contrario me preocupa que comparemos manzanas con naranjas.
DW
Correcto, la gramática será mínima en términos en no terminales. Para las reglas, esto no está claro.
Peter Leupold