Какова сложность состояния языка копирования?

Пусть будет дано число . Рассмотрим следующий язык: $n$ . $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$

Словом, - это набор строк копирования длиной . $L_n$ $2n$

Рассмотрим следующую функцию сложности состояний , в которой - это число состояний в наименьших автоматах Pushdown, которые распознают . $s$ $s(n)$ $L_n$

Вопрос: Можете ли вы формально доказать какую-либо значимую нижнюю оценку для ? $s(n)$

Моя гипотеза: . $s(n) = 2^{\Theta(n)}$

Известный верхний предел: . $s(n) \leq \mathrm{poly}(n) \cdot 2^{\frac{n}{2}}$

Правила:

(1) Алфавит стека должен быть двоичным.

(2) Лента ввода односторонняя и не может остановиться на каком-либо вводимом символе.

fl.formal-languages automata-theory grammars context-free Майкл Вехар
источник

В настоящее время у меня нет какой-либо значимой нижней границы. Мне кажется, вы могли бы доказать нижнюю границу для количества переменных, которые вам нужны для CFG, который распознает язык. Хотя я даже не совсем уверен в этом.

Майкл Вехар

Моя интуиция заключается в том, что когда вы перемещаете символы с ленты ввода в стек, вы сталкиваетесь с проблемой. Если вы когда-нибудь захотите получить эти биты позже, вы должны выбросить все биты, которые вы поместили над ним. Другими словами, кажется, что стек не помогает вам, потому что чем больше вы нажимаете на него, тем больше вы вынуждены забывать позже.

Майкл Вехар

Примечание: Для DFA (автоматов без стека) вы можете доказать нижнюю границу сложности экспоненциального состояния.

Майкл Вехар

Можете ли вы показать разумную нижнюю оценку для более простой задачи

{0^{k} 1^{l} 0^{k} 1^{l}}

$\{0^k1^l0^k1^l\}$

Андрас Саламон

Более точная верхняя граница представляется

состояниями.

(n + 3) 2^{n / 2}

$(n+3)2^{n/2}$

Андрас Саламон

Ответы:

Техника, описанная Ювалом:

Существуют ли CFG полиномиального размера, которые описывают этот конечный язык?

(вы также можете прочитать: Нижние границы размера CFG для определенных конечных языков )

$G$ $L_n$ $w\in \{0,1\}^n$ $A(w)$ $s(w)$ $ww$ $n/2$ $n$ $p(w)$ $ww$ $n/2$ $w,w'$ $A(w)=A(w')$ $p(w)=p(w')$ $2^{n/2}$ $A(w)$ $p(w)$ $2^{\Theta(n)}$

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

Джозеф Стэк
источник

Круто, еще раз спасибо! Теперь я увижу и подумаю об этом, чтобы подтвердить. :)

Майкл Вехар

[n, 2 n]

$[n,2n]$

[n / 2, n]

$[n/2,n]$ породило еще одну проблему. Мне пришлось уточнить аргументацию, аналогичную ювальской (подсчет совпадений). Теперь я считаю, что это правильно, наконец. Я отредактировал ответ и удалил мои комментарии

Джозеф Стэк

(A (w), p (w))

$(A(w),p(w))$

A (w)

$A(w)$

w w

$ww$

p (w)

$p(w)$

См. Также теорему 7 в моей статье: cs.toronto.edu/~yuvalf/CFG-LB.pdf .

Юваль Фильмус

@YuvalFilmus Стоит также отметить, что Андрас потратил немного времени, пытаясь сопоставить верхнюю и нижнюю границы. Мы с моим другом Пепе определили общий класс конечных языков и применили к ним технику. Мы никогда ничего не писали, хотя. Если у вас возникнут какие-либо проблемы, мы будем рады сотрудничать. Еще раз спасибо.

Майкл Вехар