¿Cuántos DFA aceptan dos cadenas dadas?

28

Arregle un entero n alfabeto Σ={0,1} . Defina DFA(n) como la colección de todos los autómatas de estado finito en n estados con estado inicial 1. Estamos considerando todos los DFA (no solo los conectados, mínimos o no degenerados); por lo tanto |DFA(n)|=n2n2n .

Ahora considere dos cadenas x,yΣ y defina K(x,y) como el número de elementos de DFA(n) que aceptan tanto x como y .

Pregunta: ¿Cuál es la complejidad de calcular K(x,y) ?

Esta pregunta tiene implicaciones para el aprendizaje automático .

Editar: Ahora que hay una recompensa por esta pregunta, supongo que se necesita un poco más de precisión en la formulación. Para n1 , deje que DFA(n) sea ​​la colección de n2n2n autómatas, como se definió anteriormente. Para x,y{0,1} , defina Kn(x,y) como el número de autómatas en DFA(n) que aceptan ambos x ey . Pregunta: ¿sepuede calcularKn(x,y) en el tiempopoly(n,|x|,|y|) ?

Aria
fuente
2
Si arregla un DFA sin fijar los estados finales, entonces asigna x e y al mismo estado, en cuyo caso la única restricción es que el estado tiene que ser final, o los asigna a dos estados diferentes, en cuyo caso La única restricción es que ambos tienen que ser definitivos. Por lo tanto, reformularía su problema como "¿cuántos DFA asignan xey a diferentes estados?".
a3nm
3
Aryeh, ¿puedes explicar la cuenta n2n2n ? No puedo obtener el factor 2n . Agregado: ¡Vaya! Olvidé especificar los estados finales. De todos modos, por el bien de los demás, así es como va la cuenta. Para cada estado, especifique dónde ir en las entradas 0 y 1 ; eso representa n2n . Especifique el conjunto de estados finales; eso es 2n .
Srivatsan Narayanan
2
De hecho, no me importa lo que les pase a las cadenas que no sean e y . ¿Supongo que uno necesita una cierta cantidad de puntos para comenzar una recompensa? xy
Aryeh
44
El autómata más pequeño que acepta e y tiene un solo estado, así que no creo que sea terriblemente informativo ...xy
Aryeh
3
Aquí hay una idea: solo necesitamos saber el número de DFA -estatales que terminan en el mismo estado en x e y . Deje que este número sea m y M es el número total de DFA, es decir, M = n 2 n 2 n . Entonces la respuesta es 1nxymMM=n2n2n, esto da límites. Para calcularmotra idea es que podemos olvidarnos del segmento inicial compartido dexeyy también asumir que wlogx=0ayb=1b. Solo contamos el número de DAG binarios conlestados y altura comomáximo{a,b}que0ay1bterminan en el mismo lugar y desde allí es fácil calcularm.12m+14(Mm)mxyx=0ab=1blmax{a,b}0a1bm
Kaveh

Respuestas:

1

Entonces la pregunta es bastante breve pero muy interesante. Supongo que la entrada es en unario, y x e y en binario (o tenemos problemas, como lo señala la respuesta de Kai).nxy

En primer lugar, si está interesado en conocer aproximadamente, puede generar algunos DFA aleatorios y esto le dará (whp) una buena aproximación. (Me pregunto si esta clase de complejidad tiene un nombre).K(x,y)

Entonces saber precisamente parece un problema difícil. Como a cabo en punta en los comentarios por a3_nm y Kaveh, la pregunta es equivalente a determinar el número de autómatas para la que x e y vaya al mismo estado. Denotaré la probabilidad de que vayan al mismo estado por p .K(x,y)xyp

Actualización: Algunas de las cosas que escribí aquí no eran ciertas, ahora las arreglé.

Es fácil ver que . Tenemos igualdad, si x es todo 0 e y es todo cero excepto por su último bit, que es un 1. ¿Hay otros casos? No lo sé. Si, por ejemplo, x es la cadena vacía e y = 00 , entonces p = n + 1p1/nxyxy=00 .p=n+1(n1)n

Para simplificar el problema, incluso me puse a pensar en lo que sucede si e Y son unario. Si ambos son al menos n y su diferencia es divisible por n ! , entonces p = 1 . ¿Existe una fórmula simple para la versión unaria?xynn!p=1

domotorp
fuente
He aclarado el problema: se desea un algoritmo (o una reducción de algún problema difícil conocido). La aproximación de muestreo se emplea en el documento donde se introduce este núcleo: portal.acm.org/citation.cfm?id=1577108poly(n,|x|,|y|)
Aryeh
2
En cuanto a la versión unaria: solo hay polinómicamente muchos autómatas unarios estados, por lo que apostaría a que hay un algoritmo de poli-tiempo para calcular K n ( x , y ) en este caso. nKn(x,y)
Aryeh
De hecho, tiene toda la razón en que la versión unaria es computable. Todavía me pregunto cuán simple es la fórmula para una x e y dada.
domotorp
La reducción que ha utilizado es defectuosa: x e y pueden ser aceptadas por los mismos autómatas y terminar en estados completamente diferentes, de hecho, pueden compartir solo el estado inicial en sus rutas, lo cual es cierto para todas las cadenas.
amnn
@amnn: Han pasado tres años desde que escribí esto, pero ¿el tercer párrafo de mi respuesta no explica por qué trato solo con terminar en el mismo estado?
domotorp
0

Es muy posible que me esté perdiendo el punto, pero usted declaró que es fijo, por lo que todos los DFA de ese tamaño podrían considerarse precalculados y almacenados en un formato fácilmente simulable. Calcule K de la siguiente manera:nK

En la entrada , y donde x , y Σ xyx,yΣ

  1. almacenar e yxy
  2. Inicializar el contador a 0c0
  3. para cada uno de sus DFAn2n2n
  4. a. simúlelo en ambas palabras (este paso es )O(|xy|)

    si. incremente si ambas ejecuciones de simulación aceptanc

  5. salida c

En total, el cálculo tiene una complejidad lineal. La respuesta es bastante diferente para .K(n,x,y)

Kai
fuente
3
Claramente, probar todas las máquinas funcionará. Aryeh quiere saber si hay, quizás, un algoritmo de tiempo polinómico o algún otro resultado de dureza.
Lev Reyzin
Hablando estrictamente, este es el tiempo polinómico en la entrada, si n no es parte de la entrada, eso es lo que Kai estaba diciendo. Pero la pregunta es claramente diferente.
domotorp
44
Oh ya veo. No creo que eso sea lo que él quiere decir con "arreglo ". Creo que la interpretación natural del problema es una que no lo trivializa. n
Lev Reyzin
1
Bien, gracias por señalar la escapatoria, Kai. Se ha solucionado :)
Aryeh