Dejar ser un NFA acíclico.
Ya que es acíclico es finito
Podemos calcular en tiempo polinomial?
Si no, ¿podemos aproximarlo?
Tenga en cuenta que el número de palabras no es el mismo que el número de rutas de aceptación en , que es fácilmente computable.
Permítanme mencionar un enfoque obvio que no funciona: convierta el NFA en un DFA (que también será acíclico), luego cuente el número de rutas de aceptación en el DFA. Esto no da como resultado un algoritmo de tiempo polinómico, ya que la conversión puede causar una explosión exponencial en el tamaño del DFA.
Respuestas:
Aquí hay un enfoque que espero que le brinde una aproximación de factor multiplicativo, con tiempo de ejecución polinomial.
DejarL ser un lenguaje regular que es un subconjunto de { 0 , 1}norte , p.ej, L = L ( M) ∩ { 0 , 1}norte . Intentaremos calcular el tamaño aproximado deL .
En un nivel alto, nuestro enfoque para aproximarnosEl | L | se verá algo así:
Elige una fracciónpags , dónde 0 < p < 1 .
Elige un idioma normalR tal que, más o menos, R es un subconjunto aleatorio de { 0 , 1}norte de tamaño aproximadamente pags2norte (es decir, El | R | ≈p2norte )
Comprueba siL ∩ R No está vacío. Tenga en cuenta que esta verificación se puede hacer en tiempo polinómico.
Realice repetidamente los pasos 1-3 para varios valores depags . Esto le brinda información que le permitirá aproximarseEl | L | .
En particular, siEl | L | =m entonces esperaríamos
Entonces, si eligesp = 1 / m y repita los pasos 1-3 varias veces, debería esperar ver una intersección vacía aproximadamente el 37% del tiempo. Si ve una intersección vacía significativamente más a menudo que eso, entonces aumentepags e intenta de nuevo. Si ve una intersección vacía significativamente menos frecuente que eso, podría disminuirpags e intenta de nuevo.
De esta forma, utilizando algo como la búsqueda binaria, debería poder aproximarEl | L | dentro de un factor de aproximación multiplicativo.
Aún tendrá que elegir alguna forma de elegirR para que sea regular pero también se comporte como un subconjunto aleatorio. Hay muchas posibilidades, pero una buena manera podría ser elegir un hash aleatorio 2-universalh : { 0 , 1}metro→ { 0 , 1 , 2 , … , k - 1 } recoger y∈ { 0 , 1 , ... , k - 1 } al azar, y dejar R = { x ∈ { 0 , 1}norte: h ( x ) = y} . Elegirk = ⌈ 1 / p ⌉ te da un conjunto aleatorio R de aproximadamente el tamaño correcto, y porque h es 2-universal, todas las matemáticas anteriores deberían funcionar correctamente.
Esto debería resolver su problema para el caso donde todas las cadenas en la NFA tienen la misma longitud, digamosnorte . Si tienen diferentes longitudes, puede manejar cada longitud posible por separado. Ya queMETRO es acíclico, la longitud máxima de cualquier cadena en L (M) es como máximo el número de estados en METRO , por lo que esto no aumenta demasiado el tiempo de ejecución.
(Esta construcción podría recordarle el teorema Vazirani-Vazirani sobre el SAT inequívoco).
fuente
Suponga que puede contar en tiempo polinómico el número de palabras de un idioma dado por un NFA acíclico. En este caso, considerando dos NFA acíclicosUNA1 y UNA2 , puedes calcular en tiempo polinómico el cardenal norte1 (resp. norte2 ) del lenguaje de UNA1 (resp. UNA2 ) Mediante un producto directo (preservando la aciclicidad) también puede calcular en tiempo polinómico el cardenalnorte3 de la intersección de estos dos idiomas. Los dos autómatas aceptan el mismo idioma sinorte1=norte2=norte3 . Por lo tanto, puede probar la igualdad de dos lenguajes finitos dados por autómatas acíclicos en polinomios, que se sabe que es un problema NP-completo. Entonces, a menos quePAGS= NPAGS , no puede resolver su problema en tiempo polinómico.
fuente