Contando el número de palabras aceptadas por un NFA acíclico

8

Dejar METRO ser un NFA acíclico.

Ya que METRO es acíclico L(METRO) es finito

Podemos calcular El |L(METRO)El | 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 METRO, 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.

RB
fuente
Las técnicas para llevar autómatas arbitrario sobre, véase, por ejemplo Más en cstheory.SE .
Raphael
1
@Raphael: me temo que no entiendo tu respuesta allí. Específicamente, no parece funcionar para una NFA ambigua. Contar el número de palabras en UFA es lo mismo que contar el número de rutas de aceptación, lo cual, como se menciona en la pregunta, es simple.
RB

Respuestas:

2

Aquí hay un enfoque que espero que le brinde una aproximación de factor multiplicativo, con tiempo de ejecución polinomial.

Dejar L ser un lenguaje regular que es un subconjunto de {0 0,1}norte, p.ej, L=L(METRO){0 0,1}norte. Intentaremos calcular el tamaño aproximado deL.

En un nivel alto, nuestro enfoque para aproximarnos El |LEl | se verá algo así:

  1. Elige una fracción pags, dónde 0 0<pags<1.

  2. Elige un idioma normal R tal que, más o menos, R es un subconjunto aleatorio de {0 0,1}norte de tamaño aproximadamente pags2norte (es decir, El |REl |pags2norte)

  3. Comprueba si LRNo 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 de pags. Esto le brinda información que le permitirá aproximarseEl |LEl |.

En particular, si El |LEl |=metroentonces esperaríamos

Pr[LR=]=(1-pags)metromi-pagsmetro.

Entonces, si eliges pags=1/ /metroy 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 aumentepagse 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 aproximar El |LEl | dentro de un factor de aproximación multiplicativo.

Aún tendrá que elegir alguna forma de elegir Rpara 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 0,1}metro{0 0,1,2,...,k-1}recoger y{0 0,1,...,k-1} al azar, y dejar R={X{0 0,1}norte:h(X)=y}. Elegirk=1/ /pags 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, digamos norte. 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(METRO) 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).

DW
fuente
0

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 cardenalnorte3de 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=nortePAGS, no puede resolver su problema en tiempo polinómico.

nevro
fuente
cita necesaria para el resultado de la dureza
A.Schulz