Сложность пересечения регулярных языков как контекстно-свободных грамматик

При заданных регулярных выражениях , существуют ли нетривиальные ограничения на размер наименьшей контекстно-свободной грамматики для ? $R_1, \dots, R_n$ $R_1 \cap \cdots \cap R_n$

fl.formal-languages regular-language context-free Максимум
источник

??? пытаясь визуализировать это. есть какая-то хитрость? пересечение

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

R_{n}

$R_n$

vzn

@vzn: ты прав. Проблема в том, что этот DFA и, следовательно, CFG могут быть очень большими. Мне интересно, можно ли использовать дополнительную мощность CFG для получения более краткого описания пересечения.

Макс

не догадка подозревать, что каждый CFL, который распознает (то есть эквивалентен) RL, не использует свой стек или может быть преобразован в тот, который не увеличивает состояния, и минимальный такой PDA (по количеству состояний) имеет тот же размер, что и минимальный DFA. никогда не слышал / не видел доказательств этого. это может быть не сложно? более простой вопрос, есть ли PDA, который распознает RL, который меньше, чем DFA? не думай

ВЗН

@vzn: Полезная гипотеза, но ложная: пусть

будет подмножеством языков Дика в скобках двух типов, где максимальная глубина вложения равна

. Существует CFG для

размера

, но минимальный DFA (даже, я думаю, минимальный NFA) имеет размер

L_{k}

$L_k$

k

$k$

L_{k}

$L_k$

O (k)

$O(k)$

O (2^{k})

$O(2^k)$

Макс

Дейк-языки - это КЛЛ, а не КЛ ...? но видите, что вы ограничиваете максимальную глубину вложения ... так что же вы можете создать тот же язык с пересечениями RL? что / где доказательство того, что минимальный DFA такой большой? это

состояний ? Вы не определяете критерии минимальности или где-либо еще, а состояния воспринимаете как естественный случай, но часто это не единственный случай.

O (2^{k})

$O(2^k)$

vzn

Ответы:

Это отличный вопрос, и он действительно входит в мои интересы. Я рад, что ты спросил это Макс.

Пусть дано DFA с не более чем состояниями. Было бы хорошо, если бы существовал КПК с субэкспоненциально большим количеством состояний, который принимает пересечение языков DFA. Однако я полагаю, что такой КПК не всегда может существовать. $n$ $O(n)$

Рассмотрим язык копирования. Теперь ограничимся копированием строк длиной n.

Формально рассмотрим копию $n$ $:=$ . $\{ xx \, | \, x \in \{0,1\}^{n}\}$

Мы можем представить копию как пересечение DFA с размером не более . Однако самый маленький DFA, который принимает копию, имеет состояний. $n$ $n$ $O(n)$ $n$ $2^{\Omega(n)}$

Точно так же, если мы ограничимся алфавитом бинарного стека, то я подозреваю, что наименьший КПК, который принимает копию, имеет экспоненциально много состояний. $n$

PS Не стесняйтесь, присылайте мне по электронной почте, если вы хотите обсудить дальше. :)

Майкл Вехар
источник

Я не думаю, что могут быть какие-либо нетривиальные нижние или верхние границы.
Для нижних оценок рассмотрим язык для фиксированного . Размер наименьшей контекстно-свободной грамматики является логарифмическим по размеру регулярного выражения , тогда как размер наименьшего автомата для является линейным по размеру регулярного выражения . Эта экспоненциальная разница остается неизменной, если мы пересекаем с другими такими языками. Для верхних границ рассмотрим язык , состоящий ровно из одного $L_1 = \{ a^{2^k} \}$ $k$ $L_1$ $L_1$ $L_1$ $L_1$
$L_2$ Дебрюйн-последовательность длиной . Известно, что размер наименьшей грамматики для является наихудшим, то есть $n$ $L_2$ , поэтому разница с «наименьшим» автоматом дляявляется просто логарифмическим фактором, предложение 1 в $O\left( \frac{n}{\log n} \right)$ $L_2$

D. Hucke, M. Lohrey, E. Noeth Создание маленьких грамматик дерева и малых схем для формул , которые появятся в FSTTCS 2014

Нетривиальная общая нижняя или верхняя граница противоречила бы этим результатам, так как то, что верно для пересечения языков, должно быть верно для пересечения языка. $n$ $1$

john_leo
источник

Замечание о размере наименьшей грамматики для единственной последовательности Дебрюйна довольно интересно. Не могли бы вы предоставить ссылку. Спасибо.

Майкл Вехар

Кроме того, я могу ошибаться, но кажется, что вы рассматривали проблему только для одного регулярного выражения (а не продукта регулярных выражений)?

Майкл Вехар

n

$n$

Спасибо! Вы смогли описать конкретный пример. Вот простое замечание, приводящее к существованию таких примеров. Пусть п будет дано. Есть 2 ^ n строк длины n. Кроме того, существует не более 2 ^ n машин Тьюринга с не более чем n / log (n) состояниями. Следовательно, некоторая строка x длины n такая, что ни одна машина Тьюринга с числом состояний меньше n / log (n) не принимает язык {x}. Следовательно, {x} принимается DFA с n состояниями и не может быть принято PDA с менее чем n / log (n) состояниями.

Майкл Вехар

Позвольте мне высказать второе мнение Майкла, это действительно интересный вопрос. Основная идея Михаэля может быть объединена с результатом из литературы, таким образом обеспечивая подобную нижнюю границу строгим доказательством.

$n$ $k$

$2^{k+1}$ $2^k+1$ $s$ $O(s^2)$ $O(4^{k})$

$2^{\Omega(\sqrt{k}/\log k)}$

$L_n = \{\,ww^Rw \in \{a,b\}^*\mid |w|=n\,\}$ $w^R$ $w$ $L_n$ $2n+1$

$r_i = (a+b)^ia(a+b)^{2(n-i-1)}a(a+b)^*+(a+b)^ib(a+b)^{2(n-i-1)}b(a+b)^*$ $1\le i \le n$
$s_i = (a+b)^*a(a+b)^{2(n-i-1)}a(a+b)^i+(a+b)^*b(a+b)^{2(n-i-1)}b(a+b)^i$ $1\le i \le n$
$\ell = (a+b)^{3n}$

$k$ $O(n^2)$

$L_n$ $2^n/(2n) = 2^{\Omega(\sqrt{k}/\log k)}$ $2$ $n$ $n^n/(2n)$

$O(4^n)$

Ссылки:

В. Арвинд, Пушкар, С. Джоглекар, Срикант, Сринивасан. Арифметические схемы и произведение многочленов Адамара , FSTTCS 2009, Vol. 4 из LIPIcs, с. 25-36
Ланге, Мартин; Leiß, Hans (2009). « Для CNF или нет для CNF? Эффективная, но презентабельная версия алгоритма CYK ». Informatica Didactica 8.

Герман Грубер
источник