Contar palabras aceptadas por una gramática regular

26

Dado un lenguaje regular (NFA, DFA, gramática o expresión regular), ¿cómo se puede contar el número de palabras aceptadas en un idioma determinado? Tanto "con exactamente n letras" como "con como máximo n letras" son de interés.

Margareta Ackerman tiene dos documentos sobre el tema relacionado de enumerar palabras aceptadas por una NFA, pero no pude modificarlas para contar de manera eficiente.

Parece que la naturaleza restringida de los lenguajes regulares debería hacer que contarlos sea relativamente fácil: casi espero una fórmula más que un algoritmo Desafortunadamente, mis búsquedas hasta ahora no han encontrado nada, por lo que debo estar usando los términos incorrectos.

Charles
fuente
Supongo que te refieres a "número de palabras de aceptación de tamaño ", o algo así? de lo contrario, ¿cuál es el número de palabras de aceptación para Σ nΣ
Suresh Venkat

Respuestas:

37

Para un DFA, en el que el estado inicial es el estado , el número de palabras de longitud k que terminan en el estado i es A k [ 0 , i ] , donde A es la matriz de transferencia del DFA (una matriz en la que número en la fila i y columna j es el número de símbolos de entrada diferentes que causan una transición del estado i al estado j ) Entonces puede contar aceptando palabras de longitud exactamente k fácilmente, incluso cuando k0kiAk[0,i]Aijijkk es moderadamente grande, simplemente calculando una potencia de matriz y agregando las entradas correspondientes a los estados de aceptación.

Lo mismo funciona para aceptar palabras de longitud como máximo , con una matriz ligeramente diferente. Agregue una fila y columna adicionales de la matriz, con una en la celda que esté tanto en la fila como en la columna, una en la nueva fila y la columna del estado inicial, y un cero en todas las demás celdas. El efecto de este cambio en la matriz es agregar una ruta más al estado inicial en cada potencia.k

Esto no funciona para los NFA. Sospecho que lo mejor que puede hacer es convertirlo a un DFA y luego aplicar el algoritmo de alimentación de matriz.

David Eppstein
fuente
2
La respuesta perfecta: obvia solo una vez que la hayas leído.
Charles
1
Este enfoque tiene un tiempo de ejecución exponencial en el peor de los casos si tiene una entrada que no sea un DFA. ¿No es un problema para ti, @Charles? Parece incluir expresiones regulares, NFA y gramáticas en sus preguntas, y también pide una manera eficiente.
Raphael
17

A=(Q={q1,,qn},Σ,δ,QF)q1QFQδQ×Σ×Q

Qi(z)qin[zn]Qi=|{w|w|=nw accepted from qi}|

Claramente:

Qi(z)=[qiQF]+(qi,a,qj)δxQj(z)

Q1[zn]Q1

Esto se remonta a una técnica introducida para gramáticas por Chomsky y Schützenberger (1963); se transfiere fácilmente a autómatas finitos.

εxaΣwΣkxxk

Rafael
fuente
Agradezco la nota histórica!
Charles
1
Er, este es realmente un método que funciona realmente bien (y es simple, una vez que lo obtienes) en muchas circunstancias. Por ejemplo, puede hacer CFG exactamente de la misma manera.
Raphael
1
Ya veo, entendí mal. En ese caso, si quieres leer esto, te recomiendo Kuich (1970), que encontré más accesible que el trabajo de C&S. También cubre esto en un libro suyo que no recuerdo.
Raphael
1
n
1
@joro En caso de gramáticas inequívocas, creo que esto es cierto, sí.
Raphael
7

Creo que este es un problema difícil de contar, vea este artículo: contar el tamaño de las secuencias regulares de longitud dada es # P-completo: S. Kannan, Z. Sweedyk y SR Mahaney. Recuento y generación aleatoria de cadenas en idiomas regulares. En el Simposio ACM-SIAM sobre Algoritmos discretos (SODA), páginas 551–557, 1995.

Miklós István
fuente
1
La publicación anterior supone que la longitud dada es unaria. Si, en cambio, la longitud está en binario, el problema es duro para PSPACE. Digo esto basado en la prueba de que decidir la equivalencia de dos expresiones regulares es PSPACE-hard. En esa reducción, un reg-ex fue construido para aceptar todas las cadenas, y el otro para aceptar todas las cadenas que no son válidas rechazando los historiales de cómputo de la máquina PSPACE M en la entrada w. El uso de esa segunda expresión regular y la longitud de un historial de cálculo de M en w como entradas para el problema en cuestión hace que este otro problema también sea difícil para PSPACE.
Mikhail Rudoy
3

#NC1

SamiD
fuente