¿Encuentra el DFA más pequeño que separa dos palabras sin usar la búsqueda de fuerza bruta?

23

Dadas dos cadenas x e y, quiero construir un DFA de tamaño mínimo que acepte x y rechace y. Una forma de hacerlo es la búsqueda de fuerza bruta. Enumera los DFA que comienzan con los más pequeños. Intenta cada DFA hasta que encuentre uno que acepte x y rechace y.

Quiero saber si hay alguna otra forma conocida de encontrar o construir un DFA de tamaño mínimo que acepte x y rechace y. En otras palabras, ¿podemos superar la búsqueda de fuerza bruta?

Mas detalle:

(1) Realmente quiero un algoritmo para encontrar un DFA de tamaño mínimo, no un DFA de tamaño mínimo.

(2) No solo quiero saber qué tan grande o pequeño es el DFA mínimo.

(3) Aquí, solo estoy enfocado en el caso en el que tienes dos cadenas x e y.


Editar :

Información adicional para el lector interesado:

Supongamos que e son cadenas binarias de longitud como máximo . Es un resultado conocido que hay un DFA que acepta y rechaza con como máximo estados. Observe que hay aproximadamente DFA con un alfabeto binario y como máximo estados. Por lo tanto, el enfoque de la fuerza bruta no requeriría que enumeremos más de DFA. De ello se deduce que el enfoque de la fuerza bruta no podría tomar mucho más que tiempo.xynxynnnnnnnn

Diapositivas que encontré útiles: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf

Michael Wehar
fuente
2
@ AndrásSalamon ¿Sigue siendo NP completo si los conjuntos a distinguir consisten en una sola cadena? Me parece que esto debería ser razonablemente manejable.
mhum
66
@mhum el problema de que hay muchos idiomas regulares diferentes que separan las dos cadenas: la minimización de DFA encontrará el mejor autómata para cualquiera de estos idiomas, pero no hará nada para compararlo con los autómatas para los otros idiomas de separación.
David Eppstein el
44
Si y Y son diferentes longitudes, con el mayor de longitud n , es fácil de encontrar rápidamente un AFD con O ( log n ) afirma que los separa: sólo tiene que utilizar un ciclo de longitud p , donde p no hace división | x | - | y | . Encuentre p intentando 2 , 3 , 5 , ... en orden hasta encontrar la p adecuada . Si x e y tienen la misma longitud, entonces el OxynO(logn)pp|x||y|p2,3,5,pxyconstrucción de Robson, en un artículo de 1996, proporciona una máquina simple que se puede encontrar mediante una búsqueda de tamañoO(n). Ninguna construcción está garantizada para ser el DFA más pequeño. O(n)O(n)
Jeffrey Shallit
3
Las notas de Shallit, vinculadas anteriormente, incluyen la observación útil de que el peor caso para el problema de separación es cuando el alfabeto es binario: siempre es posible dividir alfabetos más grandes en dos subconjuntos que aún distinguen las dos palabras de entrada y buscar un autómata binario que trate letras en un subconjunto como 0 y letras en el otro subconjunto como 1. Pero para buscar el autómata separador mínimo, esto no parece ayudar, ya que es posible que pueda usar la información adicional del alfabeto original para hacerlo mejor de lo que podría hacerlo con un mapeo a un alfabeto binario.
David Eppstein
3
Un caso especial de esta otra pregunta reciente en la que los tamaños de entrada y salida equivalen a 1. autómatas finitos mínimos dados en palabras y palabras . esa respuesta enumera algo de literatura de aprendizaje incluyendo algunas heurísticas.
vzn

Respuestas:

9

Si tuviera que hacer esto en la práctica, usaría un solucionador SAT.

La cuestión de si hay un DFA con estados que acepta x y rechaza y se puede expresar fácilmente como una instancia SAT. Por ejemplo, una forma es tener 2 k 2 variables booleanas: z s , b , t es verdadero si el DFA pasa del estado s al estado t en el bit de entrada b . Luego agregue algunas cláusulas para hacer cumplir que esto es un DFA, y algunas variables y cláusulas para hacer cumplir que acepta x y rechaza y .kxy2k2zs,b,tstbxy

Ahora use la búsqueda binaria en para encontrar la k más pequeña de manera que exista un DFA de este tipo. Según lo que he leído en documentos sobre problemas relacionados, esperaría que esto sea razonablemente efectivo en la práctica.kk


Otras codificaciones de esto como SAT son posibles. Por ejemplo, podemos usar una codificación de rastreo:

  • Si es de longitud m , puede agregar m lg k variables booleanas: sea s 0 , s 1 , ... , s m la secuencia de estados recorridos en la entrada x , y represente cada s i usando lg k variables booleanas.xmmlgks0,s1,,smxsilgk

  • Ahora para cada tal que x i = x j , tiene la restricción de que s i - 1 = s j - 1i,jxi=xj .si1=sj1si=sj

  • Luego, extienda esto para manejar : deje que t 0 , ... , t n sea ​​la secuencia de estados recorridos en la entrada y , y represente cada t j usando variables booleanas lg k . Para cada i , j tal que y i = y j , agregue la restricción de que t i - 1 = t j - 1yt0,,tnytjlgki,jyi=yj .ti1=tj1ti=tj

  • De manera similar, para cada tal que x i = y j , agregue la restricción que s i - 1 = t j - 1i,jxi=yj .si1=tj1si=tj

  • Ambas trazas deben comenzar desde el mismo punto de partida, por lo tanto, agregue el requisito de que (WLOG puede requerir s 0 = t 0 = 0 ).s0=t0s0=t0=0

  • Para asegurarse de que el DFA usa solo estados, requiere que 0 s i < k y 0 t j < k para todo i , j .k0si<k0tj<ki,j

  • Finalmente, para codificar el requisito de que es aceptado y y es rechazado, requiere que s mt n .xysmtn

Todos estos requisitos pueden codificarse como cláusulas SAT.

Como antes, usaría la búsqueda binaria en para encontrar la k más pequeña para la que existe tal DFA.kk

DW
fuente
3
tenga en cuenta que esto en realidad será superior a la búsqueda de fuerza bruta si hay ciertas simetrías en el problema y el solucionador las reconoce, pero actualmente puede ser difícil identificarlas / aislarlas (ya sea para humanos o máquinas). también existe alguna "tecnología" más nueva / relacionada de las teorías de módulos de satisfacción y programación de conjuntos de respuestas, algunas de las cuales tienen predicados de gráficos "incorporados" o pueden admitir sus definiciones.
vzn