2DFA que requer muitos estados no DFA equivalente?

10

Existe um 2DFA com estados (onde é não trivial, digamos, pelo menos 4) que exija pelo menos estados para simular o uso de qualquer DFA? $n$ $n$ $2^n$

Um DFA bidirecional (2DFA) é um autômato de estado finito determinístico que pode mover-se para frente e para trás em sua fita de entrada somente leitura, ao contrário dos autômatos de estado finito que só podem mover a cabeça de entrada em uma direção.

É sabido que os 2DFAs reconhecem precisamente a mesma classe de idiomas que os DFAs, ou seja, os idiomas regulares. Menos compreendida é a questão de quão eficiente é a simulação. As construções originais do final da década de 1950 de Rabin / Scott e Shepherdson usavam a noção de seqüências cruzadas e são bastante difíceis de analisar. Moshe Vardi publicou outra construção que mostra um limite superior de estados, mas esse limite pode ter alguma folga. $2^{O(n^2)}$

Estou perguntando se são conhecidas (famílias de) 2DFAs que exigem muitos estados em qualquer DFA simulando-as, mesmo após a minimização do DFA por Myhill-Nerode. Além disso, haveria conseqüências interessantes em conhecer esses 2DFAs?

Moshe Y. Vardi, uma nota sobre a redução de autômatos bidirecionais para autômatos unidirecionais, IPL 30 261–264, 1989. doi: 10.1016 / 0020-0190 (89) 90205-6 ( pré-impressão )

automata-theory lower-bounds András Salamon
fonte

8

$n(n^n -(n-1)^n)$

Também estou colocando uma figura deste artigo, dando uma imagem clara:

Para obter mais, acho que este artigo é um bom ponto de partida. Para verificar os desenvolvimentos recentes relacionados, também posso recomendar os documentos listados aqui: dblp: Christos A. Kapoutsis .

Abuzer Yakaryilmaz
fonte

11

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

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

2^{Θ (n \log n)}

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

5

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

{a, b}^{*} \cdot b \cdot {a, b}^{n} \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
fonte

(a + b)^{*}

$(a+b)^*$

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

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

n

$n$

ε

$\varepsilon$

2DFA que requer muitos estados no DFA equivalente?

Respostas: