Densidade assintótica de gramáticas ambíguas e livres de contexto (CFGs)

Qual é a proporção de CFGs ambíguos para todos os CFGs ?

Como os dois conjuntos são infinitamente contáveis, a proporção não está bem definida. Mas e a densidade assintótica :

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}$

onde símbolos terminais e não terminais provêm de um conjunto contável fixo.

O tamanho de uma gramática é qualquer noção razoável de tamanho para gramáticas, por exemplo,

o número total de ocorrências de variáveis e terminais nas regras de produção, ou
o número total de ocorrências de variável ou
o número total de regras de produção, ou
o número de variáveis distintas.

(Estou assumindo que a definição de tamanho não afetará a resposta.)

fl.formal-languages grammars context-free user18064
fonte

Como um aparte, as seguintes noções de tamanho de CFG foram consideradas na literatura: Quanto às noções de tamanho de gramática, as seguintes apareceram na literatura. (1) Número total de ocorrências de variáveis e terminais em ambos os lados de todas as produções na gramática. (2) Número de ocorrências variáveis em ambos os lados de todas as produções da gramática. (3) Número de produções na gramática. (4) Número de variáveis distintas na gramática.

Martin Berger

Veja, por exemplo: S. Ginsburg, N. Lynch, Complexidade do tamanho em formas gramaticais sem contexto. J. Gruska, Sobre o tamanho das gramáticas sem contexto. J. Gruska, Complexidade e inequívoca gramática e idiomas livres de contexto. A. Kelemenova, Complexidade de gramáticas de forma normal.

Martin Berger

@ Martin, se alguém não tomar cuidado, pode haver infinitas gramáticas sintaticamente diferentes de um determinado tamanho e a proporção não fará sentido. A maneira segura é contar o comprimento de bits de alguma codificação fixa de gramáticas.

Kaveh

Você provavelmente deseja definir a densidade assintótica como a razão de logaritmos das respectivas quantidades, uma vez que ambas as quantidades são exponenciais, provavelmente com bases diferentes.

mobius bolinho de massa

@MartinBerger Assumindo que estamos a falar a mesma coisa, isto é, definindo

, isso obviamente afetaria a densidade. Suponha que o número de CFGs não ambíguos seja

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$ e o número de CFGs é

, em seguida, o log-densidade é

2^{n}

$2^n$

enquanto a densidade assintótica é 0. Tenho certeza de que a densidade assintótica será 0 ou 1, mas a densidade logarítmica assintótica provavelmente será um número interessante.

l o g_{1.5} 2

$log_{1.5} 2$

mobius bolinho de massa

Respostas:

A questão depende da codificação exata. No entanto, parece que em muitas codificações razoáveis, como o comprimento tende ao infinito, o número de regras de produção (para uma interpretação apropriada do símbolo inicial e do terminal ) será mais de um com alta probabilidade; aqui eu quero dizer literalmente o mesmo terminal . Se considerarmos isso como ambiguidade, espero que a maioria das gramáticas seja ambígua. Também podemos inventar situações semelhantes, como as regras e $S\to a$ $S$ $a$ $a$ $S\to S$ cada aparecendo pelo menos uma vez. $S\to a$

Assumindo essa hipótese geral, de que toda regra concebível (fixa) deve aparecer com alta probabilidade à medida que o comprimento tende ao infinito, descobrimos que "a maioria" das gramáticas gera de forma ambígua. $\Sigma^*$

Como exemplo, considere a seguinte codificação para gramáticas sobre . O alfabeto gramática consiste nos símbolos . Os não terminais são indexados por cadeias binárias de comprimento pelo menos 2. As regras são separadas por pontos finais. Cada regra é uma sequência de cadeias binárias separadas por ponto e vírgula. A primeira cadeia binária é a não terminal no lado esquerdo e o restante (se houver) constitui o lado direito; se a primeira cadeia binária não for não-terminal (ou seja, , 0,1), o não-terminal inicial será assumido. O não terminal inicial é sempre 00. $\Sigma = \{0,1\}$ $\{0,1,;,.\}$ $\epsilon$

$\{0,1,;,.\}^*$ $.00;00.$ $.00;0.$

Yuval Filmus
fonte

S \to S

$S\to S$

S \to a

$S\to a$

Mas não é também o caso que, à medida que o tamanho (CFG) aumenta, o número de terminais e não terminais normalmente aumenta, então precisamos de mais bits para representá-los, portanto, precisamos de mais bits para representar regras individuais. Portanto, o número de CFGs que não são ambíguos por razões triviais (por exemplo, apenas uma regra se encaixa no tamanho limite) também aumenta.

Martin Berger

@ Martin Depende da codificação. Talvez você possa criar uma codificação que suporte sua reivindicação, por exemplo, se o tamanho do alfabeto aumentar com o tamanho da gramática. Minha codificação usa um tamanho constante de alfabeto, para que esse efeito não aconteça.

Yuval Filmus

@MartinBerger Esse é um argumento válido sobre o aumento do número de símbolos terminais e não terminais à medida que aumentamos o tamanho da gramática. Para casos de uso, como linguagens de programação, isso faz sentido.

usar o seguinte comando

@ user18064 As linguagens de programação geralmente usam um alfabeto de tamanho constante, na maioria dos casos um subconjunto de ASCII. Não conheço nenhuma linguagem prática com tamanho ilimitado de alfabeto, embora alguém possa defini-la facilmente.

Yuval Filmus