Асимптотическая плотность неоднозначных контекстно-свободных грамматик (CFG)

Каково соотношение неоднозначных CFG к всем CFG ?

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

lim_{n \mapsto \infty} \frac{# ambiguous CFG of size < n}{# CFG of size < n}

$\lim_{n \mapsto \infty}\frac {\# \text{ ambiguous CFG of size} < n} {\# \text{ CFG of size} < n}$

где терминальные и нетерминальные символы происходят из фиксированного счетного набора.

Размер грамматики - это любое разумное понятие размера для грамматики, например

общее количество вхождений переменных и терминалов в правилах производства или
общее количество вхождений переменной, или
общее количество правил производства, или
количество различных переменных.

(Я предполагаю, что определение размера не повлияет на ответ.)

fl.formal-languages grammars context-free user18064
источник

Кроме того, в литературе были рассмотрены следующие понятия размера CFG: Что касается понятия размера грамматики, то в литературе появилось следующее. (1) Общее количество вхождений переменных и терминалов с обеих сторон всех производств в грамматике. (2) Количество переменных вхождений на обеих сторонах всех производств в грамматике. (3) Количество произведений в грамматике. (4) Количество различных переменных в грамматике.

Мартин Бергер

См., Например: С. Гинзбург, Н. Линч, Сложность размера в не зависящих от контекста грамматических формах. Я. Грушка, О размерах контекстно-свободных грамматик. J. Gruska, Сложность и однозначность грамматик и языков без контекста. А. Келеменова, Сложность грамматик нормальной формы.

Мартин Бергер

@ Мартин, если не соблюдать осторожность, то может быть бесконечно много синтаксически разных грамматик заданного размера, и соотношение не будет иметь смысла. Безопасным способом является подсчет длины в битах некоторого фиксированного кодирования грамматик.

Каве

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

пельмени мобиус

@MartinBerger Если предположить, что мы говорим об одном и том же, то есть определение , это, очевидно, повлияет на плотность. Предположим, что число однозначных CFG равно а количество CFG равно , тогда логарифмическая плотность равна а асимптотическая плотность равна 0. Я вполне уверен, что асимптотическая плотность будет либо 0, либо 1, но асимптотическая логарифмическая плотность, вероятно, будет интересным числом.

l o g d e n s i t y = l o g (# u n a m b i g u o u s C F G s) / l o g (# C F G s)

$logdensity = log(\#unambiguousCFGs) / log(\#CFGs)$

{1.5}^{n}

$1.5^n$

2^{n}

$2^n$

l o g_{1.5} 2

$log_{1.5} 2$

пельмени мобиус

Ответы:

Вопрос зависит от точной кодировки. Тем не менее, кажется, что во многих разумных кодировках, поскольку длина стремится к бесконечности, число правил производства (для соответствующей интерпретации начального символа и терминала ) будет больше одного с высокой вероятностью; здесь я буквально имею в виду тот же терминал . Если мы рассмотрим это как двусмысленность, то я ожидаю, что «большинство» грамматик будет двусмысленным. Мы также можем придумать подобные ситуации, такие как правила и каждого, появляющиеся хотя бы один раз. $S\to a$ $S$ $a$ $a$ $S\to S$ $S\to a$

Предполагая эту общую гипотезу, что каждое (фиксированное) мыслимое правило должно появляться с высокой вероятностью, когда длина стремится к бесконечности, мы находим, что «большинство» грамматик генерирует неоднозначным образом. $\Sigma^*$

В качестве примера рассмотрим следующую кодировку для грамматик над . Грамматический алфавит состоит из символов . Нетерминалы индексируются двоичными строками длиной не менее 2. Правила разделяются точками. Каждое правило представляет собой последовательность двоичных строк, разделенных точкой с запятой. Первая двоичная строка является нетерминальной с левой стороны, а остальные (если таковые имеются) составляют правую часть; если первая двоичная строка не является нетерминальной (т. е. это , 0,1), то подразумевается начальная нетерминальная. Стартовый нетерминал всегда 00. $\Sigma = \{0,1\}$ $\{0,1,;,.\}$ $\epsilon$

В этой кодировке каждая строка в Описывает некоторую грамматику. Случайная грамматика с большой вероятностью будет содержать много копий $\{0,1,;,.\}^*$ $.00;00.$ а также $.00;0.$ и в частности будет неоднозначным.

Юваль Фильмус
источник

Да, я считаю такие правила, как

S \to S

$S\to S$ а также

S \to a

$S\to a$ (появляется более одного раза) в грамматике как действительный. Действительно, это делает грамматику тривиально неоднозначной. Приветствия.

user18064

Но разве это не тот случай, когда с увеличением размера (CFG) число терминалов и нетерминалов обычно увеличивается, поэтому нам нужно больше битов для их представления, следовательно, нам нужно больше битов для представления отдельных правил. Таким образом, число CFG, которые являются однозначными по тривиальным причинам (например, только одно правило соответствует размеру), также увеличивается.

Мартин Бергер

@Martin Это зависит от кодировки. Возможно, вы можете придумать кодировку, подтверждающую вашу заявку, например, если размер алфавита увеличивается с ростом грамматики. Моя кодировка использует постоянный размер алфавита, поэтому этот эффект не происходит.

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

@MartinBerger Это правильный аргумент в пользу увеличения количества терминальных и нетерминальных символов при увеличении размера грамматики. Для вариантов использования, таких как языки программирования, это имеет смысл.

user18064

@ user18064 В языках программирования обычно используется алфавит постоянного размера, в большинстве случаев это подмножество ASCII. Я не знаю ни одного практического языка с неограниченным размером алфавита, хотя их легко было бы определить.

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