2DFA, która wymaga wielu stanów w równoważnym DFA?

11

Czy istnieje 2DFA ze stanami (gdzie jest łatwe, powiedzmy co najmniej 4), które wymagają co najmniej stanów do symulacji przy użyciu dowolnego DFA? $n$ $n$ $2^n$

Dwukierunkowy DFA (2DFA) jest deterministyczny automat skończony-państwo, które może poruszać się tam iz powrotem na jej taśmie tylko do odczytu wejścia, w przeciwieństwie do automatów skończonych państwa, które mogą poruszać się tylko głowę wejściowe w jednym kierunku.

Powszechnie wiadomo, że 2DFA rozpoznają dokładnie tę samą klasę języków co DFA, innymi słowy zwykłe języki. Mniej zrozumiałe jest pytanie o efektywność symulacji. Oryginalne konstrukcje Rabin / Scott i Shepherdson z końca lat 50. XX wieku wykorzystywały pojęcie krzyżujących się sekwencji i są dość trudne do analizy. Moshe Vardi opublikował inną konstrukcję, która pokazuje górną granicę stanów , ale granica ta może mieć pewien luz. $2^{O(n^2)}$

Pytam, czy znane są (rodziny) 2DFA, które wymagają wielu stanów w dowolnym DFA symulującym je, nawet po minimalizacji DFA przez Myhill-Nerode. Ponadto, czy byłyby jakieś interesujące konsekwencje poznania takich 2DFA?

Moshe Y. Vardi, A Note on Reduction of Two-Way Automata to One-Way Automata , IPL 30 261–264, 1989. doi: 10.1016 / 0020-0190 (89) 90205-6 ( preprint )

automata-theory lower-bounds

— András Salamon
źródło

9

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

Przedstawiam również rysunek z tego artykułu, który daje jasny obraz:

Aby uzyskać więcej, uważam, że ten artykuł jest dobrym punktem wyjścia. Aby sprawdzić związane z tym ostatnie wydarzenia, mogę również polecić sprawdzenie dokumentów wymienionych tutaj: dblp: Christos A. Kapoutsis .

— Abuzer Yakaryilmaz
źródło

1

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
źródło

(a + b)^{*}

$(a+b)^*$

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

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

n

$n$

ε

$\varepsilon$