2DFA yang membutuhkan banyak negara bagian dalam DFA yang setara?

Apakah ada 2DFA dengan negara (di mana n adalah non trivial, katakan setidaknya 4) yang membutuhkan setidaknya 2 negara n untuk mensimulasikan menggunakan DFA?$n$$n$$2^n$

Sebuah dua arah DFA (2DFA) adalah deterministik finite-state automaton yang diperbolehkan untuk bergerak maju mundur pada tape read-only input, tidak seperti automata terbatas-negara yang mungkin hanya memindahkan kepala masukan dalam satu arah.

Diketahui bahwa 2DFA mengenali kelas bahasa yang sama persis dengan DFA, dengan kata lain bahasa biasa. Kurang dipahami dengan baik adalah pertanyaan tentang seberapa efisien simulasi itu. Konstruksi asli dari akhir 1950-an oleh Rabin / Scott dan Shepherdson menggunakan gagasan melintasi urutan dan cukup sulit untuk dianalisis. Moshe Vardi menerbitkan konstruksi lain yang menunjukkan batas atas menyatakan, tetapi batas ini mungkin memiliki beberapa kendur.$2^{O(n^2)}$

Saya bertanya apakah ada (keluarga) 2DFA yang diketahui yang membutuhkan banyak negara bagian dalam DFA yang mensimulasikannya, bahkan setelah Myhill-Nerode meminimalkan DFA. Selain itu, apakah akan ada konsekuensi menarik dari mengetahui 2DFA seperti itu?

• Moshe Y. Vardi, Catatan tentang Pengurangan Automata Dua Arah menjadi Automata Satu Arah , IPL 30 261–264, 1989. doi: 10.1016 / 0020-0190 (89) 90205-6 ( pracetak )

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

Saya juga meletakkan gambar dari makalah ini memberikan gambaran yang jelas:

Untuk mendapatkan lebih banyak, saya pikir makalah ini adalah titik awal yang baik. Untuk memeriksa perkembangan terakhir yang terkait, saya juga dapat merekomendasikan untuk memeriksa makalah yang tercantum di sini: dblp: Christos A. Kapoutsis .

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

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

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

$2^n$$n+c$