2DFA, который требует много состояний в эквивалентном DFA?

11

Существует ли 2DFA с состояниями (где нетривиально, скажем, по крайней мере 4), для которых требуется по крайней мере состояния для моделирования с использованием любого DFA? $n$ $n$ $2^n$

Двусторонний DFA (2DFA) является детерминированным конечным числом состояний автомата , который может перемещаться назад и вперед на его только для чтения ввода ленты, в отличие от конечно-автоматов , которые могут двигаться только входной головки в одном направлении.

Хорошо известно, что 2DFA распознают точно такой же класс языков, как и DFA, другими словами, обычные языки. Менее понятен вопрос, насколько эффективна симуляция. В оригинальных конструкциях конца 1950-х годов Рабина / Скотта и Шепердсона использовалось понятие пересекающихся последовательностей, и их довольно сложно проанализировать. Моше Варди опубликовал еще одну конструкцию, которая показывает верхнюю границу состояний, но эта граница может иметь некоторую слабину. $2^{O(n^2)}$

Я спрашиваю, известны ли какие-либо (семейства) 2DFA, для которых требуется много состояний в любом DFA, имитирующем их, даже после минимизации DFA по Myhill-Nerode. Кроме того, будут ли какие-нибудь интересные последствия знания таких 2DFA?

Моше Й. Варди, Записка о редукции двухсторонних автоматов к односторонним автоматам , IPL 30 261–264, 1989 г. doi: 10.1016 / 0020-0190 (89) 90205-6 ( препринт )

automata-theory lower-bounds Андраш Саламон
источник

9

Точная граница - это , что было дано в статье « Удаление двунаправленности из недетерминированных конечных автоматов » Кристоса Капуциса (2005). $n(n^n -(n-1)^n)$

Я также помещаю фигуру из этой статьи, которая дает ясную картину:

Чтобы получить больше, я думаю, что эта статья является хорошей отправной точкой. Чтобы проверить соответствующие недавние события, я также могу рекомендовать проверить документы, перечисленные здесь: dblp: Кристос А. Капуцис .

Абузер Якарылмаз
источник

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
источник

(a + b)^{*}

$(a+b)^*$

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

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

n

$n$

ε

$\varepsilon$

2DFA, который требует много состояний в эквивалентном DFA?

Ответы: