2DFA que requiere muchos estados en DFA equivalente?

10

¿Hay un 2DFA con estados (donde no es trivial, digamos al menos 4) que requiere al menos estados para simular usando cualquier DFA? $n$ $n$ $2^n$

Un DFA bidireccional (2DFA) es un autómata determinista de estado finito que puede moverse hacia adelante y hacia atrás en su cinta de entrada de solo lectura, a diferencia de los autómatas de estado finito que solo pueden mover el cabezal de entrada en una dirección.

Es bien sabido que los 2DFA reconocen exactamente la misma clase de lenguajes que los DFA, en otras palabras, los lenguajes regulares. Menos bien entendida es la cuestión de cuán eficiente es la simulación. Las construcciones originales de finales de la década de 1950 por Rabin / Scott y Shepherdson usaban una noción de secuencias cruzadas y son bastante difíciles de analizar. Moshe Vardi publicó otra construcción que muestra un límite superior de estados, pero este límite puede tener cierta holgura. $2^{O(n^2)}$

Me pregunto si se conocen (familias de) 2DFA que requieran muchos estados en cualquier DFA que los simule , incluso después de que Myhill-Nerode minimice el DFA. Además, ¿habría alguna consecuencia interesante de conocer tales 2DFA?

Moshe Y. Vardi, Una nota sobre la reducción de autómatas bidireccionales a autómatas unidireccionales , IPL 30 261–264, 1989. doi: 10.1016 / 0020-0190 (89) 90205-6 ( preimpresión )

automata-theory lower-bounds András Salamon
fuente

8

El límite apretado es , que se dio en Quitar la bidireccionalidad de los autómatas finitos no deterministas por Christos Kapoutsis (2005). $n(n^n -(n-1)^n)$

También estoy poniendo una figura de este documento que da una imagen clara:

Para obtener más, creo que este documento es un buen punto de partida. Para verificar los desarrollos recientes relacionados, también puedo recomendar consultar los documentos enumerados aquí: dblp: Christos A. Kapoutsis .

Abuzer Yakaryilmaz
fuente

1

2^{O (n^{2})}

$2^{O(n^2)}$

2^{Θ (n \log n)}

$2^{\Theta(n \log n)}$

5

$\Sigma = \{a,b,c\}$

{una, si}^{*} \cdot si \cdot {una, si}^{norte} \cdot C

$\{a,b\}^* \cdot b \cdot \{a,b\}^n \cdot c$

$c$ $n+1$ $c$ $b$

$n+c$ $c$ $2^n$ $n$ $\{a,b\}$ $c$ $n$ $n$ $b$

$2^n$ $n+c$

DCTLib
fuente

(a + b)^{*}

$(a+b)^*$

b \cdot (a + b)^{n} \cdot c

$b \cdot (a+b)^n \cdot c$

n

$n$

ε

$\varepsilon$

2DFA que requiere muchos estados en DFA equivalente?

Respuestas: