¿Puede la ambigüedad constante reducir la complejidad del estado de un lenguaje regular?

Decimos que NFA $M$ es constantemente ambiguo si existe $k\in \mathbb{N}$ tal que cualquier palabra $w\in \Sigma^*$ sea aceptada por $0$ o (exactamente) caminos. $k$

Si el autómata es constantemente ambiguo para , entonces se llama FA inequívoca (UFA). $M$ $k=1$ $M$

Deje que sea un lenguaje regular. $L$

¿Puede un autómata para constantemente ambiguo ser más pequeño que el UFA más pequeño que acepta ? ¿Cuánto más pequeño podría ser? $M_c$ $L$ $L$

¿Puede un autómata finito ambiguo ser exponencialmente más pequeño que el CFA más pequeño para el mismo idioma?

Se sabe que hay autómatas finitamente ambiguos (existe , de modo que cada palabra es aceptada por hasta $k$ $k$ rutas) que son exponencialmente más pequeños que el UFA más pequeño para el mismo idioma, pero no he visto algo sobre la ambigüedad constante.

Además, aquí hay una pregunta relacionada que publiqué aquí hace unos meses.

EDITAR:

La respuesta de Domotorp muestra que es polinomialmente reducible a , pero no aborda la cuestión de si podemos obtener esa reducción de espacio polinomial por s. $CFA$ $UFA$ $CFA$

Entonces, la nueva pregunta es: ¿Cuánto más pequeño (linealmente / cuadráticamente / etc.) se puede comparar un con el mínimo ? por el mismo idioma? $CFA$ $UFA$

¿están permitidas las transiciones

ϵ

$\epsilon$

Denis

Quizás esto pueda ser útil: en Kupke, Al separar constante de ambigüedad polinómica de autómatas finitos , se presenta la siguiente jerarquía:

el documento relacionado porque está detrás de Paywall.

dfa ≺_{2^{n}} unfa ≺_{2^{n}} cafa ≺_{2^{n}} ??? ≺_{2^{n}} pafa ≺_{2^{n}} n f a

$\text{dfa} \prec_{2^n} \text{unfa} \prec_{2^n} \text{cafa} \prec_{2^n} \text{???} \prec_{2^n} \text{pafa} \prec_{2^n} {nfa}$

Marzio De Biasi

Gracias @MarzioDeBiasi, pero desafortunadamente esto no ayuda (también tuve esperanzas cuando vi la presentación). Usan una notación diferente a la que yo uso (y he visto en diferentes documentos). Su "ambigüedad constante" es lo que llamé ambigüedad finita, por lo que la relación entre su Cafa y UFA ya la conocía. Dado que mi aplicación cuenta soluciones para problemas de NPC, mi lenguaje siempre es finito y, como tal, cada palabra es aceptada por

rutas, que llamaron "constante".

O (1)

$O(1)$

Me pregunto si mi definición ayuda a reducir la complejidad del estado, ya que tengo un CFA que es exponencialmente más pequeño que el UFA más pequeño que sé construir, y me preguntaba si es posible que no haya un UFA pequeño para el lenguaje.

@Denis, sí, pero ¿te ayudaría a reducir la complejidad del estado? Asumiría que solo podría reducir el número de bordes mediante tales movimientos.

Respuestas:

Afirmo que si para algún idioma hay un CFA con estados y o $s$ $0$ $c$ aceptan rutas para cada palabra, entonces hay un UFA con estados. La idea básica es que los estados de la UFA son las tuplas c (ordenadas) de los estados del CFA y acepta si y solo si todos los estados c aceptan. Por supuesto, también tenemos que asegurarnos de que se trata de cálculos diferentes y que no contamos todos los permutaciones, por lo que para estos necesitamos algunos adicionales $C_ss^c$ $c!$ $C_s$ bits de almacenamiento.

Una descripción un poco más detallada de la idea básica: si es un estado de la UFA, entonces tiene una transición de la misma (leyendo alguna letra ) al estado si y solo si el CFA tiene una transición (leyendo la letra ) de a para cada . Un estado $(s_1,\ldots,s_c)$ $a$ $(s_1',\ldots,s_c')$ $a$ $s_i$ $s_i'$ $i$ $(s_1,\ldots,s_c)$ está aceptando si y solo si está aceptando para cada . Por supuesto, el estado inicial de la UFA es $s_i$ $i$ donde es el estado inicial de la CFA. $(s_0,\ldots,s_0)$ $s_0$

El problema con lo anterior es que las corridas simuladas del CFA podrían ser las mismas. Entonces, agregamos información adicional, codificada, por ejemplo, en un gráfico en vértices que tiene un borde entre el vértice y el vértice si durante la ejecución hasta ahora al menos una vez que tuvimos ese . $c$ $c$ $i$ $j$ $c_i\ne c_j$

Ahora todavía tenemos un problema, que hemos contado todo veces debido a las posibles permutaciones. Podemos remediar esto exigiendo que si los estados -ésimo y -ésimo hayan sido los mismos hasta ahora y en el siguiente paso serían diferentes, entonces en el siguiente paso el estado -ésimo debería tener un índice más grande. $c!$ $i$ $j$ $i$

domotorp
fuente

Gracias por contestar @domotorp. Lamentablemente, no puedo decir que lo entiendo. ¿Puede dar más detalles (p. Ej., ¿Cómo se codificaría la prueba de primalidad?). Gracias !

De todos modos, me di cuenta de que también hay un UFA para ese idioma, así que olvídalo. ¿Qué pasa con la parte restante de mi respuesta?

domotorp

No estoy seguro de seguirlo. Si

es CFA con

, entonces no significa que solo podría haber caminos

para cada palabra

, solo que

de ellos terminará en un estado de aceptación. ¿Cuáles serían los estados de la UFA? ¿Puedes intentar formalizarlo?

M

$M$

k = c

$k=c$

c

$c$

w

$w$

c

$c$

Ahí tienes, espero que ahora esté claro.

domotorp